# Isoperimetric Formulas for Hyperbolic Animals

Érika Roldán  Zentrum Mathematik, TU München, Garching b. München, Germany
<EMAIL_ADDRESS>and  Rosemberg Toala-Enriquez  Maths Learning Centre,
De Montfort University<EMAIL_ADDRESS>
###### Abstract.

An animal is a planar shape formed by attaching congruent regular polygons
along their edges. In 1976, Harary and Harborth gave closed isoperimetric
formulas for Euclidean animals. Here, we provide analogous formulas for
hyperbolic animals. We do this by proving a connection between Sturmian words
and the parameters of a discrete analogue of balls in the graph determined by
hyperbolic tessellations. This reveals a complexity in hyperbolic animals that
is not present in Euclidean animals.

###### Key words and phrases:

Extremal combinatorics, enumerative combinatorics, polyforms, polyominoes,
polyiamonds, hexiamonds, animals, hyperbolic tessellations, isoperimetric
inequalities.

###### 2020 Mathematics Subject Classification:

00A69, 05A16, 05A20, 05B50, 52B60, 52C05, 05C07, 05C10, 52C20, 05D99

##  1\. Introduction

An _animal_ is a planar shape with a connected interior consisting of a finite
number of tiles on a regular tessellation of the plane. Using Schläfli’s
notation, a $\\{p,q\\}$-tessellation consists of tiling the plane with regular
$p$-gons with exactly $q$ of these polygons meeting at each vertex. We call an
animal living in a $\\{p,q\\}$-tessellation a $\\{p,q\\}$-animal. The polygons
forming an animal are called tiles. We define the perimeter to be the number
of edges that are in the boundary of the animal. Let
$\mathcal{P}^{p,q}_{min}(n)$ be the minimum perimeter that a
$\\{p,q\\}$-animal with $n$ tiles can have. In 1976 [1], Harary and Harborth
gave the following isoperimetric formulas for Euclidean animals, that is, for
all $\\{p,q\\}$-animals such that $(p-2)(q-2)=4$.

$\displaystyle\mathcal{P}^{3,6}_{min}(n)$
$\displaystyle=2\left\lceil\frac{1}{2}(n+\sqrt{6n})\right\rceil-n,$
$\displaystyle\mathcal{P}_{min}^{4,4}(n)$ $\displaystyle=2\left\lceil
2\sqrt{n}\right\rceil,$ $\displaystyle\mathcal{P}_{min}^{6,3}(n)$
$\displaystyle=2\left\lceil\sqrt{12n-3}\right\rceil.$

Harary and Harborth called animals attaining minimum perimeter extremal
animals. To our surprise, for almost 50 years, isoperimetric formulas for
hyperbolic animals were unknown and in general extremal hyperbolic animals
were unstudied. Recently [2], Malen, Roldán and Toalá-Enríquez gave a
constructive way of generating a sequence of extremal hyperbolic animals that
follows a spiral pattern—See Figure 1. Based on these extremal spiral animals
they were able to provide a recursive way of computing
$\mathcal{P}^{p,q}_{min}(n)$ for hyperbolic animals. Nevertheless, a closed
formula for $\mathcal{P}^{p,q}_{min}(n)$ with $(p-2)(q-2)>4$ was still
missing. Here, we provide these closed formulas.

In our main result, we prove that for all $(p-2)(q-2)>4$ and $n>p(q-2)$,

(1.1)
$\displaystyle\mathcal{P}_{min}^{p,q}(n)=\left(p-2-\frac{2}{\beta}\right)n+\epsilon_{p,q}(n),$

where $\epsilon_{p,q}(n)$ is an error term that we explicitly define in
Theorem 1.5, Section 1.1 and that is uniformly bounded for all $p,q,n$. The
constant $\beta$ depends only on $p$ and $q$ and is given by

(1.2) $\beta=\frac{(p-2)(q-2)+\sqrt{(p-2)^{2}(q-2)^{2}-4(p-2)(q-2)}}{2(p-2)}.$

For $n\leq p(q-2)$, the error term in Formula (1.1) takes a different form.
For completeness, we will also provide isoperimetric formulas for these values
of $n$.

Figure 1. Examples of extremal hyperbolic animals [2]. Here we show spiral
animals with 37 tiles for the hyperbolic cases $\\{3,7\\},\\{4,5\\}$, and
$\\{7,3\\}$.

###  1.1. Main Results

For the rest of the paper, unless otherwise stated, we assume that $\\{p,q\\}$
corresponds to an hyperbolic tessellation, that is, $(p-2)(q-2)>4$.

Let $\alpha$ be the solution of the quadratic equation
$\alpha^{2}+2\alpha+1=(p-2)(q-2)\alpha$ that fulfils $\alpha>1$. The constants
$\alpha$ and $\beta$ are related by

(1.3) $\displaystyle\beta=\frac{\alpha+1}{p-2}=\frac{q-2}{\alpha^{-1}+1}.$

We define the sequences $\\{n_{k}\\}$ and $\\{l_{k}\\}$, for $k\geq 1$, as

(1.4) $\displaystyle n_{k}$
$\displaystyle=1+\frac{p(q-2)}{\alpha-\alpha^{-1}}\left(\frac{\alpha^{k}-1}{\alpha-1}-\frac{\alpha^{-k}-1}{\alpha^{-1}-1}\right),\quad\text{and}\quad
l_{k}=\frac{n_{k+1}-n_{k}}{p}.$

Now we have all the ingredients to state our main result.

######  Theorem 1.5.

Let $(p-2)(q-2)>4$, $n>p(q-2)$, $k$ such that $n_{k}<n\leq n_{k+1}$,

$n^{\prime}=n-n_{k}-\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor\cdot
l_{k},$

and

(1.6) $\displaystyle\phi_{k}=\begin{cases}\alpha^{-k}(\alpha-1)&\text{if $p=3$
and }n^{\prime}\leq\frac{l_{k}+l_{k+1}}{q-2},\text{ or if $p=4$},\\\
\alpha^{-k}(\alpha(\alpha-1)+1),&\text{if $p=3$ and
}\frac{l_{k}+l_{k+1}}{q-2}<n^{\prime}\leq l_{k},\\\
\alpha^{-k}(\alpha-\beta)&\text{if $p>4$}.\end{cases}$

If we define

$\epsilon_{p,q}(n)=\frac{2n}{\beta}+2\left\lfloor
1+\frac{1}{\beta}+\frac{p}{\alpha-1}+\frac{p\alpha^{-k}}{\alpha^{-1}-1}+\frac{\phi_{k}}{\beta}+\alpha^{-k}\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor-\frac{n}{\beta}\right\rfloor-2\left\lfloor\frac{n-n_{k}}{n_{k+1}-n_{k}}\right\rfloor,$

then

(1.7)
$\displaystyle\mathcal{P}_{min}^{p,q}(n)=\left(p-2-\frac{2}{\beta}\right)n+\epsilon_{p,q}(n).$

Using the definition of $n_{k}$, the condition $n_{k}<n\leq n_{k+1}$ is
equivalent to

(1.8) $\displaystyle
k=\left\lfloor\log_{\alpha}\left(\frac{\Delta+\sqrt{\Delta^{2}-4\alpha}}{2}\right)\right\rfloor,\quad\text{where}\quad\Delta=\alpha+1+\frac{(n-2)(\alpha-1)(\alpha-\alpha^{-1})}{p(q-2)}.$

This gives a formula for computing $k$ for any $n\geq 1$. Thus, equation (1.7)
is a closed formula for $\mathcal{P}_{min}^{p,q}(n)$ valid for $n>p(q-2)$. For
$n\leq p(q-2)$ the values of $\mathcal{P}_{min}^{p,q}(n)$ can be obtained by
following the spiral construction of extremal animals defined in [2], and
analyzing the increment (of either $p-2$ or $p-4$) when a new tile is
attached. This results in the following formulas

$\displaystyle\mathcal{P}_{min}^{p,q}(n)=\begin{cases}p+(p-2)(n-1),&\text{ if
}1\leq n<q,\\\
p+(p-2)\left(n-1-\left\lfloor\frac{n-2}{q-2}\right\rfloor\right)+(p-4)\left\lfloor\frac{n-2}{q-2}\right\rfloor,&\text{
if }q\leq n<p(q-2),\\\ p(p-3)+(q-3)(p-2)p,&\text{ if }n=p(q-2).\\\
\end{cases}$

It is not clear from Theorem 1.5 what is the asymptotic behaviour of
$\mathcal{P}_{min}^{p,q}(n)$. To accomplish this, we prove in the following
Theorem that $\epsilon_{p,q}(n)$ is uniformly bounded by a constant.

######  Theorem 1.9.

Let $n>p(q-2)$ and $\epsilon_{p,q}(n)$ be defined as above. Then,
$0<\epsilon_{p,q}(n)<22$. Moreover, for $n>n_{4}$,

(1.10)
$\displaystyle\left|\epsilon_{p,q}(n)-2\left(1+\frac{1}{\beta}+\frac{p}{\alpha-1}\right)\right|<2.6.$

######  Corollary 1.11.

Let $(p-2)(q-2)>4$, then

(1.12)
$\displaystyle\mathcal{P}_{min}^{p,q}(n)=\left(p-2-\frac{2}{\beta}\right)n+o(1).$

The rest of the paper is structured as follows: in Section 2, we describe how
Sturmian words arise from the study of the degrees (i.e., the number of edges
adjacent to a vertex) of the perimeter vertices of a certain sequence of
extremal hyperbolic animals. In the same section, in Theorem 2.3, we give a
closed formula for the values of these degrees. In Section 3, we use this
formula to prove Theorem 1.5 and Theorem 1.9. For clarity of exposition, we
have postponed the proof of Theorem 1.5 and some of the painful algebraic
computations needed along the paper to Sections 4 and 5, respectively.

##  2\. Extremal hyperbolic animals and Sturmian words

We use the following construction of sequences of extremal hyperbolic animals
introduced in [2].

######  Definition 2.1.

Denote by $A_{p,q}(1)$ the animal with only one $p$-gon. Then, construct
$A_{p,q}(k)$ from $A_{p,q}(k-1)$ by adding precisely the tiles needed so that
all the perimeter vertices of $A_{p,q}(k-1)$ get surrounded by $q$ tiles. We
call $A_{p,q}(k)$ the _complete $k$-layered $\\{p,q\\}$-animal_. Let $d_{k}$
be the word obtained by concatenating the degrees of the perimeter vertices of
$A_{p,q}(k)$. Denote by $n_{k}$ and $P_{k}$ the number of tiles and the
perimeter of $A_{p,q}(k)$, respectively.111In Theorem 3.1 of [2] it was proven
that $n_{k}$ satisfies Equation (3.1).

In what follows we use the abbreviation $2^{a}$ to describe a string of $a$
consecutive 2’s. The expressions $3^{a}$, $4^{a}$, etc., are interpreted
similarly. If $a=0$ then we have an empty block.

On the one hand, in [2], the words $d_{k}$ were computed recursively in the
following manner: $d_{1}$ is the word $2^{p}$; then, $d_{k}$ is constructed
from $d_{k-1}$ by replacing each element of $d_{k-1}$ with a string according
to the rules contained in Table 1. Figure 2 depicts the geometric reasoning
behind these substitution rules.

Table 1. Table showing substitution rules for words $d_{k}$. Cases |  $p=3$ and $q\geq 7$ |  $p\geq 4$and $q\geq 4$ |  $p\geq 7$ and $q=3$
---|---|---|---
| $2\to 43^{q-4}$ | $2\to 32^{p-4}\left(32^{p-3}\right)^{q-3}$ | $2\to 32^{p-4}$
Substitution | $3\to 43^{q-5}$ | $3\to 32^{p-4}\left(32^{p-3}\right)^{q-4}$ | $32\to 32^{p-5}$
| $4\to 43^{q-6}$ |  |

Figure 2. Left: When $p=3$, each vertex of degree $d=3$ or $4$ in
$A_{p,q}(k-1)$ contributes to a vertex of degree 4 in $A_{p,q}(k)$ and $q-d-2$
vertices of degree equal to $3$. Center: When $p\geq 4$, each vertex of degree
equal to $3$ in $A_{p,q}(k-1)$ contributes to $q-3$ vertices of degree $3$ in
$A_{p,q}(k)$ and $(q-3)(p-3)-1$ vertices of degree $2$. Right: When $q=3$,
each vertex of degree $3$ in $A_{p,q}(k-1)$ is paired up with a vertex of
degree $2$ they together contribute to a vertex of degree $3$ and $p-5$
vertices of degree $2$ in $A_{p,q}(k)$. The other vertices of degree $2$ in
$A_{p,q}(k-1)$ contribute to a vertex of degree $3$ and $p-4$ vertices of
degree $2$ in $A_{p,q}(k)$.

On the other hand, the substitution rules of Table 1 can be rephrased if we
define the word sequences $U_{k}$ and $W_{k}$ as in Table 2. Then
$d_{k}=(U_{k})^{p}$ if $p>3$, and $k\geq 1$. If $p=3$, and $k\geq 2$, then
$d_{k}=(U_{k}U_{k-1})^{3}$.

Table 2. Table showing equations for recurrences of words $U_{k}$ and $W_{k}$. Cases |  $p=3$ and $q\geq 7$ |  $p\geq 4$ and $q\geq 4$ |  $p\geq 7$ and $q=3$
---|---|---|---
| $U_{1}=3,\,W_{1}=4$ | $U_{1}=2,\,W_{1}=3$ | $U_{1}=2,\,W_{1}=32$
Recurrence | $U_{k+1}=W_{k}U_{k}^{q-5}$ | $U_{k+1}=W_{k}U_{k}^{p-4}\left(W_{k}U_{k}^{p-3}\right)^{q-3}$ | $U_{k+1}=W_{k}U_{k}^{p-5}$
| $W_{k+1}=W_{k}U_{k}^{q-6}$ | $W_{k+1}=W_{k}U_{k}^{p-4}\left(W_{k}U_{k}^{p-3}\right)^{q-4}$ | $W_{k+1}=W_{k}U_{k}^{p-6}$

We will use the theory of Sturmian words to find closed formulas for the
$i$-th element of $W_{k}$, $U_{k}$ and $d_{k}$. To do so, we relate the
Sturmian word of $\beta$ with the limit word of the nested sequence of words
$W_{k}$, that we represent by $W=\lim_{k\to\infty}W_{k}$.

######  Definition 2.2.

Let $\beta$ be as in (1.2), define the sequence

$B(i)=\lfloor(i+1)\beta\rfloor-\lfloor i\beta\rfloor-\lfloor\beta\rfloor$

for $i\geq 1$. Let $B$ be the word obtained by concatenating the elements of
the sequence $\\{B(i)\\}_{i\geq 1}$. $B$ is known as the Sturmian word of
$\beta$.

Shallit proved in 1991 [3], that $B$ can also be constructed in the following
recursive way: let $[b_{0};b_{1},b_{2},b_{3},\dots]$ be the continued fraction
expansion of $\beta$, then $B$ is equal to $\lim_{k\to\infty}B_{k}$, where,

$\displaystyle B_{0}$ $\displaystyle=0,$ $\displaystyle B_{1}$
$\displaystyle=0^{b_{1}-1}1,$ $\displaystyle B_{k}$
$\displaystyle=B_{k-1}^{b_{k}}B_{k-2},n\geq 2.$

Using these two characterizations of the Sturmian word of $\beta$, we prove in
Section 5 the following Theorem that gives a closed formula for the elements
of $W$.

######  Theorem 2.3.

Let $\beta$ be as in (1.2). The $i$-th element of $W=\lim_{k\to\infty}W_{k}$
is equal to

(2.4) $\displaystyle q-\lfloor i\beta\rfloor+\lfloor(i-1)\beta\rfloor.$

##  3\. Proof of Theorem 1.5 and Theorem 1.9

We remind the reader that sequence of animals $A_{p,q}(k)$, that was defined
in Definition 2.1, has $n_{k}$ tiles with

(3.1)
$n_{k}=1+\frac{p(q-2)}{\alpha-\alpha^{-1}}\left(\frac{\alpha^{k}-1}{\alpha-1}-\frac{\alpha^{-k}-1}{\alpha^{-1}-1}\right).$

In [2], it was proved that $A_{p,q}(k)$ is extremal and its perimeter is

(3.2)
$\mathcal{P}_{min}^{p,q}(n_{k})=\frac{p}{\alpha-\alpha^{-1}}\left(\alpha^{k}-\alpha^{-k}+\alpha^{k-1}-\alpha^{-(k-1)}\right).$

To streamline the notation, in what follows we denote
$\mathcal{P}_{min}^{p,q}(n_{k})$ by $P_{k}$. Using Equations (3.2) and (3.1)
we prove the following Lemma that we use as an essential ingredient for
proving Theorem 1.5.

######  Lemma 3.3.

Let $k\geq 1$, the perimeter $P_{k}$ and number of tiles $n_{k}$ of
$A_{p,q}(k)$ satisfy the following equation

(3.4) $\displaystyle
P_{k}-\left(p-2\right)n_{k}=2\left(\frac{p}{\alpha-1}+\frac{p\cdot\alpha^{-k}}{\alpha^{-1}-1}+1+\frac{1}{\beta}-\frac{n_{k}}{\beta}\right).$

###### Proof.

This follows from Equations (3.1) and (3.2). The details of these calculations
can be found in Section 5. ∎

Let $n>1$ and consider $k$ such that $n_{k}<n\leq n_{k+1}$. Let $m=m(n)$ be
the integer number greater or equal than $0$ defined by the condition

(3.5) $\displaystyle\sum_{i=1}^{m}(q-d_{k}(i))\leq
n-n_{k}-1<\sum_{i=1}^{m+1}(q-d_{k}(i)),$

where $d_{k}(i)$ denotes the $i$-th element of the word $d_{k}$. The sum on
the left is interpreted as $0$ for $m=0$.

Here, we prove the following closed formula for $m$ in terms of $n$.

######  Lemma 3.6.

Consider $k\geq 2$, and $n$ such that $n_{k}<n\leq n_{k+1}$. Let
$l_{k}=\dfrac{n_{k+1}-n_{k}}{p}$, and
$n^{\prime}=n-n_{k}-\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor\cdot
l_{k}$. If $m$ satisfies Equation (3.5), then

(3.7) $\displaystyle
m(n)=\left\lfloor\frac{n-n_{k}-\phi_{k}}{\beta}-\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor\cdot\alpha^{-k}\right\rfloor+\left\lfloor\frac{n-n_{k}}{n_{k+1}-n_{k}}\right\rfloor.$

Where $\phi_{k}$ is given by equation (1.6).

###### Proof.

Theorem 2.3 give us a formula for the $i$-th element of $W$, with this we get
a formula for the $i$-th element of $U_{k}$. Then it is possible to invert
condition (3.5), thanks to the structure of $d_{k}$ in terms of $U_{k}$. The
details of the calculations can be found in Section 5. ∎

Now we have all the ingredients to prove Theorem 1.5.

###### Proof of Theorem 1.5.

In [2], it is shown that

(3.8) $\displaystyle\mathcal{P}_{min}^{p,q}(n)$
$\displaystyle=(p-2)(n-n_{k})+P_{k}-2m.$

Simplifying the expression in Equation (3.8) using Lemmas 3.3 and 3.6 we
obtain the expression for $\mathcal{P}_{min}^{p,q}(n)$ given in Equation
(1.7). ∎

The rest of this section is devoted to the proof of Theorem 1.9.

######  Lemma 3.9.

For all $p,q$, the following inequalities hold

(3.10)
$\displaystyle\frac{1}{\alpha}<0.4,\quad\frac{1}{\beta}<1.4,\quad\frac{p}{\alpha-1}<4.4,\quad\frac{\phi_{2}}{\beta}<2.8,\quad\text{and}\quad\frac{p}{\alpha^{2}}<1.1.$

###### Proof.

We claim that the maxima of
$\frac{1}{\alpha},\frac{1}{\beta},\frac{p}{\alpha-1},\frac{\phi_{2}}{\beta},\frac{p}{\alpha^{2}}$
are attained at the smallest values of $p,q$. Then the bounds are found by
evaluating at the cases $\\{p,q\\}=\\{3,7\\},\\{4,5\\},\\{5,4\\},\\{7,3\\}$.
Details can be found in Section 5.

∎

###### Proof of Theorem 1.9.

Now we prove the bounds on $\epsilon_{p,q}(n)$. Recall that $\alpha>1$ and
$k\geq 2$, note that

$\displaystyle\frac{\epsilon_{p,q}(n)}{2}$
$\displaystyle\leq\frac{n}{\beta}+1+\frac{1}{\beta}+\frac{p}{\alpha-1}+\frac{p\alpha^{-k}}{\alpha^{-1}-1}+\frac{\phi_{k}}{\beta}+\alpha^{-k}\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor-\frac{n}{\beta}$
$\displaystyle\leq
1+\frac{1}{\beta}+\frac{p}{\alpha-1}+\frac{\phi_{k}}{\beta}+\alpha^{-k}p$
$\displaystyle\leq
1+\frac{1}{\beta}+\frac{p}{\alpha-1}+\frac{\phi_{2}}{\beta}+\alpha^{-2}p.$

Where, we have used $\frac{p}{\alpha^{-1}-1}<0$ and
$\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor\leq p$. Using Lemma 3.9, we
conclude

$\displaystyle\epsilon_{p,q}(n)\leq
2\left(1+\frac{1}{\beta}+\frac{p}{\alpha-1}+\frac{\phi_{2}}{\beta}+\alpha^{-2}p\right)<2\left(1+1.4+4.4+2.8+1.1\right)<22.$

Now, using Equation (3.4), we know

$\displaystyle\epsilon_{p,q}(n_{k+1})$
$\displaystyle=\mathcal{P}_{min}^{p,q}(n_{k+1})-\left(p-2-\frac{2}{\beta}\right)n_{k+1}$
$\displaystyle=2\left(\frac{p}{\alpha-1}+\frac{p\alpha^{-(k+1)}}{\alpha^{-1}-1}+1+\frac{1}{\beta}\right)\geq
2\left(1+\frac{1}{\beta}\right).$

And for, $n_{k}<n<n_{k+1}$, we get

$\displaystyle\frac{\epsilon_{p,q}(n)}{2}$
$\displaystyle\geq\frac{n}{\beta}+\left(1+\frac{1}{\beta}+\frac{p}{\alpha-1}+\frac{p\alpha^{-k}}{\alpha^{-1}-1}+\frac{\phi_{k}}{\beta}+\alpha^{-k}\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor-\frac{n}{\beta}-1\right)$
$\displaystyle\geq\frac{1}{\beta}+\frac{p}{\alpha-1}+\frac{p\alpha^{-k}}{\alpha^{-1}-1}=\frac{1}{\beta}+\frac{p}{\alpha-1}-\frac{p\alpha^{-(k-1)}}{\alpha-1}\geq\frac{1}{\beta}.$

Thus, $\epsilon_{p,q}(n)>0$ for all $n$.

Now we prove bound (1.10). For $n=n_{k+1}$, and $k\geq 2$,

$\displaystyle\left|\epsilon_{p,q}(n_{k+1})-2\left(1+\frac{p}{\alpha-1}+\frac{1}{\beta}\right)\right|$
$\displaystyle=\left|\frac{2p\alpha^{-(k+1)}}{\alpha^{-1}-1}\right|=\frac{2p\alpha^{-k}}{\alpha-1}$
$\displaystyle\leq\frac{2p\alpha^{-2}}{\alpha-1}=\frac{2p}{\alpha-1}\cdot\frac{1}{\alpha^{2}}<2\cdot
4.4\cdot(0.4)^{2}<1.5.$

For $n_{k}<n<n_{k+1}$ and $k\geq 4$,

$\displaystyle-\frac{2p\alpha^{-(k-1)}}{\alpha-1}-2$
$\displaystyle<\epsilon_{p,q}(n_{k+1})-2\left(1+\frac{p}{\alpha-1}+\frac{1}{\beta}\right)<\frac{2\phi_{k}}{\beta}+\frac{2p}{\alpha^{k}}$
$\displaystyle-\frac{2p\alpha^{-3}}{\alpha-1}-2$
$\displaystyle<\epsilon_{p,q}(n_{k+1})-2\left(1+\frac{p}{\alpha-1}+\frac{1}{\beta}\right)<\frac{2\phi_{2}}{\alpha^{2}\beta}+\frac{2p}{\alpha^{4}}$
$\displaystyle-1.5\cdot 0.4-2$
$\displaystyle<\epsilon_{p,q}(n_{k+1})-2\left(1+\frac{p}{\alpha-1}+\frac{1}{\beta}\right)<2\cdot
2.8(0.4)^{2}+2\cdot 1.1(0.4)^{2}$ $\displaystyle-2.6$
$\displaystyle<\epsilon_{p,q}(n_{k+1})-2\left(1+\frac{p}{\alpha-1}+\frac{1}{\beta}\right)<1.3.$

This concludes the proof of Theorem 1.9.

∎

##  4\. Proof of Theorem 2.3

To prove Theorem 2.3, we begin by finding the continued fraction expansion of
$\beta$. Then we use Shallit’s Theorem to prove that the Sturmian word of
$\beta$ and the word $W$ are essentially the same. We do this in Lemmas 4.1
and 4.3, respectively.

######  Lemma 4.1.

The continued fraction expansion of $\beta$ is

$\displaystyle[q-4;\overline{1,q-6}],$ if $p=3$ and $q\geq 7$,
$\displaystyle[q-3;\overline{2,q-4}],$ if $p=4$ and $q\geq 5$,
$\displaystyle[q-3;\overline{1,p-4,1,q-4}],$ $\displaystyle\text{ if }p,q>4,$
$\displaystyle[1;1,\overline{p-4,2}],$ if $p\geq 5$ and $q=4$,
$\displaystyle[0;1,p-5,\overline{1,p-6}],$ if $p\geq 7$ and $q=3$.

###### Proof.

$\beta$ satisfies the quadratic equation
$(p-2)\beta^{2}-(p-2)(q-2)\beta+q-2=0$, then
$(p-2)\beta^{2}=(p-2)(q-2)\beta-(q-2)$. If $p,q>4$, note that
$0<\frac{q-2}{(p-2)\beta}<1$, so

$\displaystyle\beta$
$\displaystyle=q-2-\frac{q-2}{(p-2)\beta}=q-3+\frac{(p-2)\beta-(q-2)}{(p-2)\beta}$
$\displaystyle=q-3+\frac{1}{\frac{(p-2)\beta}{(p-2)\beta-(q-2)}}=q-3+\frac{1}{1+\frac{q-2}{(p-2)\beta-(q-2)}}$
$\displaystyle=q-3+\frac{1}{1+\frac{1}{\frac{(p-2)\beta-(q-2)}{q-2}}}=q-3+\frac{1}{1+\frac{1}{p-3-\frac{1}{\beta}}}$
$\displaystyle=q-3+\frac{1}{1+\frac{1}{p-4+\frac{\beta-1}{\beta}}}=q-3+\frac{1}{1+\frac{1}{p-4+\frac{1}{\frac{\beta}{\beta-1}}}}$
$\displaystyle=q-3+\frac{1}{1+\frac{1}{p-4+\frac{1}{1+\frac{1}{\beta-1}}}}=q-3+\frac{1}{1+\frac{1}{p-4+\frac{1}{1+\frac{1}{q-4+\dots}}}}$

By continuing in this way we obtain $\beta=[q-3;\overline{1,p-4,1,q-4}]$ for
$p,q>4$. The remaining cases are analogous. ∎

Recall that $B$ is the Sturmian word of $\beta$—See Definition 2.2. The
following result gives us a recursive way of describing $B$ through the
continued fraction expansion of $\beta$.

######  Theorem 4.2 (Shallit [3]).

Let $\beta$ be an irrational number with continued fraction expansion
$[b_{0};b_{1},b_{2},b_{3},\dots]$. Define

$\displaystyle B_{0}$ $\displaystyle=0,$ $\displaystyle B_{1}$
$\displaystyle=0^{b_{1}-1}1,$ $\displaystyle B_{k}$
$\displaystyle=B_{k-1}^{b_{k}}B_{k-2},\quad\text{for}\quad n\geq 2.$

Then $B=\lim_{k\to\infty}B_{k}$.

We now use Shallit’s Theorem to show that $W$ and $B$ are closely related. To
make the relation between $W$ and $B$ more transparent we introduce the words
$C_{k},D_{k}$ defined by the recurrence equations contained in Table 3. Note
that these are the same recurrence relations as $U_{k}$ and $W_{k}$, that we
defined in Table 2, but starting at 1 and 0, respectively.

Table 3. Table showing equations for recurrences of words $C_{k}$ and $D_{k}$. Cases |  $p=3$ and $q\geq 7$ |  $p\geq 4$ and $q\geq 4$ |  $p\geq 7$ and $q=3$
---|---|---|---
| $C_{1}=1,\,D_{1}=0$ | $C_{1}=1,\,D_{1}=0$ | $C_{1}=1,\,D_{1}=01$
Recurrence | $C_{k+1}=D_{k}C_{k}^{q-5}$ | $C_{k+1}=D_{k}C_{k}^{p-4}\left(D_{k}C_{k}^{p-3}\right)^{q-3}$ | $C_{k+1}=D_{k}C_{k}^{p-5}$
| $D_{k+1}=D_{k}C_{k}^{q-6}$ | $D_{k+1}=D_{k}C_{k}^{p-4}\left(D_{k}C_{k}^{p-3}\right)^{q-4}$ | $D_{k+1}=D_{k}C_{k}^{p-6}$

Let $D=\lim_{k\to\infty}D_{k}$. Observe that $D(i)=4-W(i)$, if $p=3$, and
$D(i)=3-W(i)$, if $p>3$.

######  Lemma 4.3.

Denote by $D(i)$ and $B(i)$ the $i$-th elements of the words $D$ and $B$,
respectively. Then $D(i)=B(i-1)$.

###### Proof.

Denote by $D_{k}^{\prime}$ the word $D_{k}$ without its first (left-most)
digit. That digit is always 0, i.e., $D_{k}=0D_{k}^{\prime}$.

Fix $p,q>4$. We claim that, for $k\geq 1$,

(4.4) $\displaystyle 0B_{4k-3}D_{k}^{\prime}$ $\displaystyle=D_{k}C_{k},$
(4.5) $\displaystyle B_{4k-2}$ $\displaystyle=D_{k}^{\prime}C_{k}^{p-4}0,$
(4.6) $\displaystyle 0B_{4k-1}D_{k+1}^{\prime}$ $\displaystyle=C_{k+1},$ (4.7)
$\displaystyle B_{4k}$ $\displaystyle=D_{k+1}^{\prime}0.$

We prove these relations by induction. The continued fraction expansion of
$\beta$ for $p,q>4$ is $[q-3;\overline{1,p-4,1,q-4}]$. Then, Shallit’s
recurrence relations, stated in Theorem 4.2, for $k\geq 1$, give

$\displaystyle B_{4k+1}$ $\displaystyle=B_{4k}B_{4k-1},$ $\displaystyle
B_{4k+2}$ $\displaystyle=B_{4k+1}^{p-4}B_{4k}.$ $\displaystyle B_{4k+3}$
$\displaystyle=B_{4k+2}B_{4k+1},$ $\displaystyle B_{4k+4}$
$\displaystyle=B_{4k+3}^{q-4}B_{4k+2}.$

Also, $B_{1}=1$, $B_{2}=1^{p-4}0$, $B_{3}=1^{p-4}01$,
$B_{4}=1^{p-4}\left(01^{p-3}\right)^{q-4}0$, and
$D_{2}=01^{p-4}\left(01^{p-3}\right)^{q-4}$,
$C_{2}=01^{p-4}\left(01^{p-3}\right)^{q-3}$ . So, equations (4.4)-(4.7) hold
for $k=1$. Assume these equations are also true for $k>1$. Then,

$\displaystyle 0B_{4k+1}D_{k+1}^{\prime}$
$\displaystyle=0B_{4k}B_{4k-1}D_{k+1}^{\prime}$
$\displaystyle=0D^{\prime}_{k+1}0B_{4k-1}D_{k+1}^{\prime}$
$\displaystyle=D_{k+1}C_{k+1}.$

Similarly,

$\displaystyle B_{4k+2}$
$\displaystyle=B_{4k+1}^{p-4}B_{4k}=\left(B_{4k}B_{4k-1}\right)^{p-4}B_{4k}$
$\displaystyle=\left(D_{k+1}^{\prime}0B_{4k-1}\right)^{p-4}D_{k+1}^{\prime}0=D_{k+1}^{\prime}\left(0B_{4k-1}D_{k+1}^{\prime}\right)^{p-4}0$
$\displaystyle=D_{k+1}^{\prime}C_{k+1}^{p-4}0.$

Also,

$\displaystyle 0B_{4k+3}D_{k+2}^{\prime}$
$\displaystyle=0B_{4k+2}B_{4k+1}D_{k+2}^{\prime}$
$\displaystyle=0\left(D_{k+1}^{\prime}C_{k+1}^{p-4}0\right)B_{4k+1}D^{\prime}_{k+1}C_{k+1}^{p-4}\left(D_{k+1}C_{k+1}^{p-3}\right)^{q-4}$
$\displaystyle=D_{k+1}C_{k+1}^{p-4}\left(0B_{4k+1}D^{\prime}_{k+1}\right)C_{k+1}^{p-4}\left(D_{k+1}C_{k+1}^{p-3}\right)^{q-4}$
$\displaystyle=D_{k+1}C_{k+1}^{p-4}\left(D_{k+1}C_{k+1}\right)C_{k+1}^{p-4}\left(D_{k+1}C_{k+1}^{p-3}\right)^{q-4}=C_{k+2}.$

Finally

$\displaystyle B_{4k+4}$
$\displaystyle=B_{4k+3}^{q-4}B_{4k+2}=\left(B_{4k+2}B_{4k+1}\right)^{q-4}B_{4k+2}$
$\displaystyle=\left(D_{k+1}^{\prime}C_{k+1}^{p-4}0B_{4k+1}\right)^{q-4}D_{k+1}^{\prime}C_{k+1}^{p-4}0=D_{k+1}^{\prime}C_{k+1}^{p-4}\left(0B_{4k+1}D_{k+1}^{\prime}C_{k+1}^{p-4}\right)^{q-4}0$
$\displaystyle=D_{k+1}^{\prime}C_{k+1}^{p-4}\left(D_{k+1}C_{k+1}C_{k+1}^{p-4}\right)^{q-4}0=D_{k+2}^{\prime}0$

This finishes the induction.

For the cases $\\{p=4,q\geq 5\\}$, $\\{p\geq 5,q=4\\}$, $\\{p=3,q\geq 7\\}$,
and $\\{p\geq 7,q=3\\}$, instead of Equations (4.4)-(4.7), the following holds

(4.8) $\displaystyle 0B_{2k-1}D_{k+1}^{\prime}=C_{k+1},\text{ if }q\neq
4,\quad$ $\displaystyle\text{ or }\quad
D_{k+1}0B_{2k-1}D_{k+1}^{\prime}=C_{k+1},\text{ if }q=4,$ (4.9)
$\displaystyle\,\,\,B_{2k}$ $\displaystyle=D_{k+1}^{\prime}0.$

A proof by induction of Equations (4.8) and (4.9) is analogous as before.

We conclude, by Equations (4.7) and (4.9), that $D(i)=B(i-1)$ for all $p,q$. ∎

###### Proof of Theorem 2.3.

From Lemma 4.3, for all $p$ and $q$ such that $(p-2)(q-2)>4$, we have that

$\displaystyle W(i)=\begin{cases}4-B(i-1),&\text{ if }p=3,\\\ 3-B(i-1),&\text{
if }p>3.\\\ \end{cases}$

From Lemma 4.1, we know that

$\displaystyle\lfloor\beta\rfloor=\begin{cases}q-4,&\text{ if }p=3,\\\
q-3,&\text{ if }p>3.\\\ \end{cases}$

Then, we get

$\displaystyle W(i)$ $\displaystyle=q-\lfloor\beta\rfloor-B(i-1)=q-\lfloor
i\beta\rfloor+\lfloor(i-1)\beta\rfloor.$

∎

##  5\. Proof of Lemma 3.3, Lemma 3.6 and Lemma 3.9

###### Proof of Lemma 3.3.

We compute $P_{k}-(p-2)(n_{k}-1)$ and factor by $\alpha^{k}$-terms and
$\alpha^{-k}$-terms.

$\displaystyle\big{(}P_{k}-(p-2)(n_{k}-1)\big{)}\left(\frac{\alpha-\alpha^{-1}}{p}\right)$
$\displaystyle=\alpha^{k}+\alpha^{k-1}-(p-2)(q-2)\left(\frac{\alpha^{k}-1}{\alpha-1}\right)$
$\displaystyle\quad-\alpha^{-k}-\alpha^{-(k-1)}+(p-2)(q-2)\left(\frac{\alpha^{-k}-1}{\alpha^{-1}-1}\right)$
$\displaystyle=\frac{\alpha^{k+1}+\alpha^{k}-\alpha^{k}-\alpha^{k-1}-(p-2)(q-2)(\alpha^{k}-1)}{\alpha-1}$
$\displaystyle\quad-\frac{\alpha^{-(k+1)}+\alpha^{-k}-\alpha^{-k}-\alpha^{-(k-1)}-(p-2)(q-2)(\alpha^{-k}-1)}{\alpha^{-1}-1}.$

Recall that $\alpha$ satisfies the cuadratic equation
$\alpha^{2}+2\alpha+1=(p-2)(q-2)\alpha$. It follows that
$\alpha^{k+1}+2\alpha^{k}+\alpha^{k-1}=(p-2)(q-2)a^{k}$ for $k\geq 1$. Thus,
when we substitute this expression we obtain

$\displaystyle\big{(}P_{k}-(p-2)$
$\displaystyle(n_{k}-1)\big{)}\left(\frac{\alpha-\alpha^{-1}}{p}\right)=$
$\displaystyle=\frac{\alpha^{k+1}-\alpha^{k-1}-(\alpha^{k+1}+2\alpha^{k}+\alpha^{-k})+(p-2)(q-2)}{\alpha-1}$
$\displaystyle\quad-\frac{\alpha^{-(k+1)}-\alpha^{-(k-1)}-(\alpha^{-(k+1)}+2\alpha^{-k}+\alpha^{-(k-1)})+(p-2)(q-2)}{\alpha^{-1}-1}$
$\displaystyle=\frac{-2\alpha^{k}(1+\alpha^{-1})+2(1+\alpha^{-1})-2(1+\alpha^{-1})+(p-2)(q-2)}{\alpha-1}$
$\displaystyle\quad-\frac{-2\alpha^{-k}(1+\alpha^{-1})+2\alpha^{-k-1}-2\alpha^{-k+1}+2(1+\alpha^{-1})-2(1+\alpha^{-1})+(p-2)(q-2)}{\alpha^{-1}-1}$
$\displaystyle=\frac{-2(\alpha^{k}-1)(1+\alpha^{-1})}{\alpha-1}+\frac{2(\alpha^{-k}-1)(1+\alpha^{-1})}{\alpha^{-1}-1}$
$\displaystyle\quad+\frac{-2(1+\alpha^{-1})+(p-2)(q-2)}{\alpha-1}-\frac{2\alpha^{-k}(\alpha^{-1}-\alpha)-2(1+\alpha^{-1})+(p-2)(q-2)}{\alpha^{-1}-1}.$

Now,
$n_{k}-1=\frac{p(q-2)}{\alpha-\alpha^{-1}}\left(\frac{\alpha^{k}-1}{\alpha-1}-\frac{\alpha^{-k}-1}{\alpha^{-1}-1}\right),$
and $\alpha+2+\alpha^{-1}=(p-2)(q-2)$, so

$\displaystyle P_{k}-(p-2)(n_{k}-1)$
$\displaystyle=\frac{-2(n_{k}-1)(1+\alpha^{-1})}{q-2}+\frac{p}{\alpha-\alpha^{-1}}\left(\frac{\alpha-\alpha^{-1}}{\alpha-1}-\frac{2\alpha^{-k}(\alpha^{-1}-\alpha)+\alpha-\alpha^{-1}}{\alpha^{-1}-1}\right)$

Finally, we use that $\beta=\frac{q-2}{1+\alpha^{-1}}$ and rearrange terms to
obtain

$\displaystyle P_{k}-(p-2)n_{k}$
$\displaystyle=\frac{-2(n_{k}-1)}{\beta}+\frac{p}{\alpha-1}-\frac{p}{\alpha^{-1}-1}-(p-2)+\frac{2p\alpha^{-k}}{\alpha^{-1}-1}.$

This is equivalent to (3.4). ∎

Let $\gamma_{k}=\frac{\alpha^{k}-\alpha^{-k}}{\alpha-\alpha^{-1}}$, then
$\gamma_{k+1}+2\gamma_{k}+\gamma_{k-1}=(p-2)(q-2)\gamma_{k}$. Since
$\gamma_{0}=0$ and $\gamma_{1}=1$, it follows that $\gamma_{k}$ is an integer
for all $k\geq 1$.

######  Lemma 5.1.

Let $U_{k}$ and $W_{k}$ be the words defined in Table 2, and let $u_{k}$ and
$w_{k}$ be their length, respectively. Then,

(5.2) $\displaystyle u_{k}=\begin{cases}\gamma_{k},\\\
\gamma_{k}+\gamma_{k-1},\\\
\gamma_{k}+\gamma_{k-1},\end{cases}w_{k}=\begin{cases}\gamma_{k}-\gamma_{k-1},&\text{if
$p=3,q\geq 7$ ,}\\\ \gamma_{k}-(p-3)\gamma_{k-1},&\text{if $p,q\geq 4$,}\\\
\gamma_{k}-\gamma_{k-2},&\text{if $p\geq 7,q=3$.}\end{cases}$

###### Proof.

From the definition of the words $U_{k}$ and $W_{k}$, their lengths satisfy
the following recurrence relations for the cases $p=3$, $p,q\geq 4$, and
$q=3$, respectively.

(5.3) $\displaystyle u_{k+1}=\begin{cases}(q-5)u_{k}+w_{k},\\\
((q-3)(p-3)+(p-4))u_{k}+(q-2)w_{k},\\\ (p-5)u_{k}+w_{k},\end{cases}$ (5.4)
$\displaystyle w_{k+1}=\begin{cases}(q-6)u_{k}+w_{k},\\\
((q-4)(p-3)+(p-4))u_{k}+(q-2)w_{k},\\\ (p-6)u_{k}+w_{k},\end{cases}$

Formulas (5.3) and (5.4) hold for $k=0$. Then an induction argument proves the
result for any $k\geq 1$.

∎

###### Proof of Lemma 3.6.

Denote by $W(i)$, $U_{k}(i)$ the $i$-th element of the words $W=\lim W_{k}$,
$U_{k}$, respectively. Recall that,

$\displaystyle W_{k+1}=\begin{cases}W_{k}U_{k}^{q-6},&\text{if $p=3,q\geq
7$}\\\ W_{k}U_{k}^{p-4}\left(W_{k}U_{k}^{p-3}\right)^{q-4},&\text{if $p,q\geq
4$}\\\ W_{k}U_{k}^{p-6},&\text{if $p\geq 7,q=3$}.\end{cases}$

Combining this with formula $W(i)=q-\lfloor
i\beta\rfloor+\lfloor(i-1)\beta\rfloor$ of Theorem 2.3 we obtain,

(5.5) $\displaystyle
U_{k}(i)=\begin{cases}W(i+w_{k})=q-\lfloor(i+w_{k})\beta\rfloor+\lfloor(i-1+w_{k})\beta\rfloor,&\text{if
$p=3$ or $p>4$}\\\
W(i+2w_{k})=q-\lfloor(i+2w_{k})\beta\rfloor+\lfloor(i-1+2w_{k})\beta\rfloor,&\text{if
$p=4$}\\\ \end{cases}$

Now, $d_{k}=(U_{k})^{p}$, if $p>3,k\geq 1$; and $d_{k}=(U_{k}U_{k-1})^{3}$ if
$p=3,k\geq 2$. In either case, $d_{k}$ consists of $p$ identical blocks, each
of length $\gamma_{k}+\gamma_{k-1}$.

Recall that $m=m(n)$ satisfies:

$\displaystyle\sum_{i=1}^{m}(q-d_{k}(i))\leq
n-n_{k}-1<\sum_{i=1}^{m+1}(q-d_{k}(i)).$

For all $p$, the expression
$p\cdot\sum_{i=1}^{\gamma_{k}+\gamma_{k-1}}(q-d_{k,i})$ counts number of tiles
in the $k+1$ layer of $A_{p,q}(k+1)$. That is,
$\sum_{i=1}^{\gamma_{k}+\gamma_{k-1}}(q-d_{k,i})=l_{k}$, where

$\displaystyle l_{k}$ $\displaystyle=\frac{n_{k+1}-n_{k}}{p}$
$\displaystyle=\frac{q-2}{\alpha-\alpha^{-1}}\left(\frac{\alpha^{k+1}-1}{\alpha-1}-\frac{\alpha^{-(k+1)}-1}{\alpha^{-1}-1}-\frac{\alpha^{k}-1}{\alpha-1}+\frac{\alpha^{-k}-1}{\alpha^{-1}-1}\right)$
$\displaystyle=\frac{q-2}{\alpha-\alpha^{-1}}\left(\frac{\alpha^{k+1}-\alpha^{k}}{\alpha-1}-\frac{\alpha^{-(k+1)}-\alpha^{-k}}{\alpha^{-1}-1}\right)$
$\displaystyle=(q-2)\gamma_{k}=\frac{\gamma_{k+1}+2\gamma_{k}+\gamma_{k-1}}{p-2}$

If $p=3$, we have $\beta=\alpha+1$, $u_{k}=\gamma_{k}$,
$w_{k}=\gamma_{k}-\gamma_{k-1}$. Note that
$\gamma_{k+1}-\gamma_{k}\alpha=\alpha^{-k}$ and $w_{k}\alpha-
w_{k+1}=\alpha^{-k}(\alpha-1)$. Thus, if $p=3$,

$\displaystyle\sum_{i=1}^{\gamma_{k}}(q-d_{k}(i))$
$\displaystyle=\sum_{i=1}^{\gamma_{k}}(q-U_{k}(i))=\lfloor(u_{k}+w_{k})\beta\rfloor-\lfloor
w_{k}\beta\rfloor$ $\displaystyle=\lfloor
u_{k+1}+w_{k+1}+u_{k}+w_{k}+\alpha^{-k}(\alpha-2)\beta\rfloor-\lfloor
w_{k+1}+w_{k}+\alpha^{-k}(\alpha-1)\rfloor$
$\displaystyle=u_{k+1}+u_{k}=\gamma_{k+1}+\gamma_{k}=\frac{l_{k+1}+l_{k}}{q-2}.$

Summarizing

(5.6) $\displaystyle 0$ $\displaystyle\leq m\leq\gamma_{k}+\gamma_{k-1}$
$\displaystyle\Longleftrightarrow$ $\displaystyle 1\leq n-n_{k}\leq l_{k}$
$\displaystyle\text{ if }p>3,$ (5.7) $\displaystyle 0$ $\displaystyle\leq
m\leq\gamma_{k}$ $\displaystyle\Longleftrightarrow$ $\displaystyle 1\leq
n-n_{k}\leq\gamma_{k+1}+\gamma_{k}$ $\displaystyle\text{ if }p=3.$

We now deduce a formula for $m=m(n)$, when $m$ and $n$ are within the values
given by (5.6) and (5.7). In this range, $d_{k}(i)=U_{k}(i)$ for $i\leq m$,
and we can write the condition (3.5) for $m=m(n)$ as:

$\displaystyle\sum_{i=1}^{m}(q-U_{k}(i))$ $\displaystyle\leq
n-n_{k}-1<\sum_{i=1}^{m+1}(q-U_{k}(i)),$ $\displaystyle\lfloor(m+\delta
w_{k})\beta\rfloor-\lfloor\delta w_{k}\beta\rfloor$ $\displaystyle\leq
n-n_{k}-1<\lfloor(m+1+\delta w_{k})\beta\rfloor-\lfloor\delta
w_{k}\beta\rfloor.$

Where $\delta=1$ if $p=3$ or $p>4$, and $\delta=2$ if $p=4$. The left-hand
side implies,

$\displaystyle m\beta+\delta w_{k}\beta-1-\lfloor\delta w_{k}\beta\rfloor$
$\displaystyle<n-n_{k}-1,$ $\displaystyle m$
$\displaystyle<\frac{n-n_{k}-\\{\delta w_{k}\beta\\}}{\beta}.$

Where $\\{\delta w_{k}\beta\\}=\delta w_{k}\beta-\lfloor\delta
w_{k}\beta\rfloor$. Similarly, the right-hand side implies,

$\displaystyle\frac{n-n_{k}-\\{\delta w_{k}\beta\\}-\beta}{\beta}<m.$

Since the difference between these bounds is 1, we arrive at the following
formula:

(5.10) $\displaystyle m(n)=\left\lfloor\frac{n-n_{k}-\\{\delta
w_{k}\beta\\}}{\beta}\right\rfloor,\text{ for }\begin{array}[]{l}1\leq
n-n_{k}\leq l_{k},\qquad\quad\text{ if }p>3,\\\ 1\leq
n-n_{k}\leq\gamma_{k+1}+\gamma_{k}\,\text{ if }p=3.\end{array}$

The explicit value of $\\{\delta w_{k}\beta\\}=\delta w_{k}\beta-\lfloor\delta
w_{k}\beta\rfloor$ can be computed using
$\gamma_{k+1}-\gamma_{k}\alpha=\alpha^{-k}$ and $\beta=\frac{\alpha+1}{p-2}$,
obtaining:

$\displaystyle\\{\delta
w_{k}\beta\\}=\begin{cases}\alpha^{-k}(\alpha-1)&\text{if $p=3$ or $4$},\\\
\alpha^{-k}(\alpha-\beta)&\text{if $p>4$}.\end{cases}$

Equation (5.10) is the key ingredient for Lemma 3.6. It is only left to use
the structure of $d_{k}$ in $p$ blocks. When $p>3$, we have $d_{k}=U_{k}^{p}$,
and the length of $U_{k}$ is $\gamma_{k}+\gamma_{k-1}$. Now, for any $1\leq
n-n_{k}<p\cdot l_{k}$, let

$\displaystyle j$
$\displaystyle=\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor,$
$\displaystyle n^{\prime}$ $\displaystyle=n-n_{k}-j\cdot l_{k}.$

Then $0\leq j\leq p-1$ is the position of the block of $d_{k}$ to which $m(n)$
belongs, and $n^{\prime}$ is the number of the position of the $(n-n_{k})$-th
tile within that block.

Let $m^{\prime}=m(n^{\prime})$. If $p>3$ we can apply Equation (5.10). If
$p=3$, then $d_{k}=(U_{k}U_{k-1})^{3}$, and we have to consider whether
$m^{\prime}$ falls in a $U_{k}$-block or a $U_{k-1}$-block. Taking this into
consideration we arrive at:

$\displaystyle
m^{\prime}=\begin{cases}\vspace{.1cm}\left\lfloor\frac{n^{\prime}-\alpha^{-k}(\alpha-\beta)}{\beta}\right\rfloor,&\text{
if }p>4,\\\
\vspace{.1cm}\left\lfloor\frac{n^{\prime}-\alpha^{-k}(\alpha-1)}{\beta}\right\rfloor,&\text{
if }p=3\text{ and }n^{\prime}\leq\gamma_{k+1}+\gamma_{k}\text{ or if }p=4,\\\
\left\lfloor\frac{n^{\prime}-(\gamma_{k+1}+\gamma_{k})-\\{w_{k-1}\beta\\}}{\beta}\right\rfloor+\gamma_{k},&\text{
if }p=3\text{ and }\gamma_{k+1}+\gamma_{k}<n^{\prime}\leq l_{k}.\end{cases}$

Finally, $m(n)=m^{\prime}+j(\gamma_{k}+\gamma_{k-1})$, for all $1\leq
n-n_{k}\leq p\cdot l_{k}$. Now we simplify the expression for $m^{\prime}$ for
the last case. For $p=3$, we have
$\\{w_{k-1}\beta\\}=\alpha^{-(k-1)}(\alpha-1)$, so:

$\displaystyle\left\lfloor\frac{n^{\prime}-(\gamma_{k+1}+\gamma_{k})-\\{w_{k-1}\beta\\}}{\beta}\right\rfloor+\gamma_{k}$
$\displaystyle=\left\lfloor\frac{n^{\prime}-(\gamma_{k+1}+\gamma_{k})-\alpha^{-(k-1)}(\alpha-1)+\beta\gamma_{k}}{\beta}\right\rfloor$

We use $\beta=\alpha+1$ (valid for $p=3$) and
$\alpha\gamma_{k}=\gamma_{k+1}-\alpha^{-k}$:

$\displaystyle\left\lfloor\frac{n^{\prime}-(\gamma_{k+1}+\gamma_{k})-\\{w_{k-1}\beta\\}}{\beta}\right\rfloor+\gamma_{k}$
$\displaystyle=\left\lfloor\frac{n^{\prime}-(\gamma_{k+1}+\gamma_{k})-\alpha^{-(k-1)}(\alpha-1)+\gamma_{k+1}-\alpha^{-k}+\gamma_{k}}{\beta}\right\rfloor$
$\displaystyle=\left\lfloor\frac{n^{\prime}-\alpha^{-k}(\alpha(\alpha-1)+1)}{\beta}\right\rfloor$

Summarizing, for any $p$, we can write $m$ as:

$\displaystyle m$
$\displaystyle=m^{\prime}+j(\gamma_{k}+\gamma_{k-1})=\left\lfloor\frac{n^{\prime}-\phi_{k}}{\beta}\right\rfloor+j(\gamma_{k}+\gamma_{k-1}),$

where $\phi_{k}$ is defined as in (1.6).

Now, we simplify the formula for $m$ using the fact that
$\frac{l_{k}}{\beta}-(\gamma_{k}+\gamma_{k-1})=\alpha^{-k}$.

$\displaystyle m$ $\displaystyle=m^{\prime}+j(\gamma_{k}+\gamma_{k-1}),$
$\displaystyle=\left\lfloor\frac{n-n_{k}-\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor\cdot
l_{k}-\phi_{k}}{\beta}\right\rfloor+\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor(\gamma_{k}+\gamma_{k-1})$
$\displaystyle=\left\lfloor\frac{n-n_{k}-\phi_{k}}{\beta}+\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor(\gamma_{k}+\gamma_{k-1})-\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor\frac{l_{k}}{\beta}\right\rfloor$
$\displaystyle=\left\lfloor\frac{n-n_{k}-\phi_{k}}{\beta}-\left\lfloor\frac{n-n_{k}-1}{l_{k}}\right\rfloor\cdot\alpha^{-k}\right\rfloor.$

Finally, when $n=n_{k+1}$ there is a deficit of 1 in Equation (3.5), it gives
the value of $m=p(\gamma_{k}+\gamma_{k-1})-1$. This comes from the fact that,
when we attach a new tile, we are counting the vertex trapped between the
$k$th layer and the previously attached tiles. But when we attach the
$n=n_{k+1}$ tile, we are closing the $(k+1)$-layer, so we surround two
vertices as opposed to just one. To correct for this special case, we need to
add the term $\left\lfloor\frac{n-n_{k}}{n_{k+1}-n_{k}}\right\rfloor$ to the
previous formula, thus arriving at equation (3.7).

∎

Finally, we prove the bounds that we used in the proof of Lemma 3.9.

###### Proof of Lemma 3.9.

We say that a function $F=F(p,q)$ is increasing in $p,q$ if $F$ is increasing
in $p$ while $q$ remains constant, and if $F$ is increasing in $q$ while $p$
remains constant. The same convention is adopted for decreasing in $p,q$. We
use this concept to bound functions by its values at the cases
$\\{p,q\\}=\\{3,7\\},\\{4,5\\},\\{5,4\\},\\{7,3\\}$.

For example, $t=(p-2)(q-2)-2$ is increasing in $p,q$, then so is
$\alpha=\frac{t+\sqrt{t^{2}-4}}{2}$. On the other hand, $\alpha^{-1}$ is
decreasing in $p,q$, then so is $\frac{1}{\beta}=\frac{\alpha^{-1}+1}{q-2}$.
Therefore $\frac{1}{\beta}$ is bounded by its biggest value on the cases
$\\{p,q\\}=\\{3,7\\},\\{4,5\\},\\{5,4\\},\\{7,3\\}$. Then it can be verified
that $\frac{1}{\beta}<1.4$ for all $p,q$. Similarly $\frac{1}{\alpha}<0.4$

Next, $\frac{t}{p}=\frac{pq-2p-2q+2}{p}=q-2-\frac{q-2}{p}$ is increasing in
$p,q$. Similarly $\frac{t+1}{p}$, $\frac{t-1}{p}$ and $\frac{t-2}{p}$ are
increasing in $p,q$. By composition of increasing functions, we obtain that

$\displaystyle\frac{\alpha}{p}=\frac{1}{2}\left(\frac{t}{p}+\sqrt{\left(\frac{t}{p}\right)^{4}-\frac{4}{p}}\right)$

is also increasing in $p,q$. Then, $\frac{p}{\alpha}$ is decreasing in $p,q$.
By evaluating at the cases
$\\{p,q\\}=\\{3,7\\},\\{4,5\\},\\{5,4\\},\\{7,3\\}$, we find that
$\frac{p}{\alpha}<2.7$.

Similarly

$\displaystyle\frac{\alpha-1}{p}=\frac{1}{2}\left(\frac{t-2}{p}+\sqrt{\left(\frac{t}{p}\right)^{4}-\frac{4}{p}}\right)$

is increasing in $p,q$. So $\frac{p}{\alpha-1}$ is decreasing in $p,q$. We
find that $\frac{p}{\alpha-1}<4.4$.

Now, we bound $\frac{\phi_{2}}{\beta}$ for all its cases:

$\displaystyle\frac{\alpha-1}{\alpha^{2}\beta}<\frac{1}{\alpha\beta}<\frac{1}{\beta}<1.4,$
$\displaystyle\frac{\alpha(\alpha-1)+1}{\alpha^{2}\beta}=\frac{\alpha-1}{\alpha\beta}+\frac{1}{\alpha^{2}\beta}<\frac{2}{\beta}<2.8,$
$\displaystyle\frac{\alpha-\beta}{\alpha\beta}=\frac{1}{\beta}-\frac{1}{\alpha}=\frac{p+2}{\alpha+1}-\frac{1}{\alpha}=\frac{(p-3)\alpha-1}{\alpha(\alpha+1)}<\frac{(p-3)\alpha}{\alpha(\alpha+1)}<\frac{p}{\alpha+1}<\frac{p}{t}<2.4.$

In conclusion, $\frac{\phi_{2}}{\beta}<2.8$ for all $p,q$. Finally,

$\displaystyle\frac{p}{\alpha^{2}}=\frac{p}{\alpha}\cdot\frac{1}{\alpha}<2.7\cdot
0.4<1.1.$

∎

### Acknowledgements

This project received funding from the European Union’s Horizon 2020 research
and innovation program under the Marie Skłodowska-Curie grant agreement No.
754462. This research has also been supported by the DFG Collaborative
Research Center SFB/TRR 109 Discretization in Geometry and Dynamics. The first
author thanks the Laboratory for Topology and Neuroscience for hosting them
during part of the project.

## References

  * [1] Frank Harary and Heiko Harborth, _Extremal animals_ , J. Combinatorics Information Syst. Sci. 1 (1976), no. 1, 1–8. MR 0457263
  * [2] Greg Malen, Érika Roldán, and Rosemberg Toalá-Enríquez, _Extremal $\\{p,q\\}$-animals_, arXiv preprint arXiv:2109.05331 (2021).
  * [3] Jeffrey Shallit, _Characteristic words as fixed points of homomorphisms_ , University of Waterloo. Department of Computer Science, 1991.


# Video Rescaling Networks with Joint Optimization Strategies
for Downscaling and Upscaling

Yan-Cheng Huang*1  ] Yi-Hsin Chen*1 Both authors contributed equally to this
work. ]* Cheng-You Lu1
Hui-Po Wang2 Wen-Hsiao Peng1 Ching-Chun Huang1

{s0756722.iie07g 1 National Yang Ming Chiao Tung University, Taiwan
2 CISPA Helmholtz Center for Information Security  yhchen.iie07g
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>{wpeng<EMAIL_ADDRESS>
###### Abstract

This paper addresses the video rescaling task, which arises from the needs of
adapting the video spatial resolution to suit individual viewing devices. We
aim to jointly optimize video downscaling and upscaling as a combined task.
Most recent studies focus on image-based solutions, which do not consider
temporal information. We present two joint optimization approaches based on
invertible neural networks with coupling layers. Our Long Short-Term Memory
Video Rescaling Network (LSTM-VRN) leverages temporal information in the low-
resolution video to form an explicit prediction of the missing high-frequency
information for upscaling. Our Multi-input Multi-output Video Rescaling
Network (MIMO-VRN) proposes a new strategy for downscaling and upscaling a
group of video frames simultaneously. Not only do they outperform the image-
based invertible model in terms of quantitative and qualitative results, but
also show much improved upscaling quality than the video rescaling methods
without joint optimization. To our best knowledge, this work is the first
attempt at the joint optimization of video downscaling and upscaling.

##  1 Introduction

With the increasing popularity of video capturing devices, a tremendous amount
of high-resolution (HR) videos are shot every day. These HR videos are often
downscaled to save storage space and streaming bandwidth, or to fit screens
with lower resolutions. It is also common that the downscaled videos need to
be upscaled for display on HR monitors [11, 16, 22, 2, 29].

(a) SISO-down-SISO-up

(b) SISO-down-MISO-up

(c) MIMO-down-MIMO-up (the proposed method)

Figure 1: Comparison of video rescaling frameworks according to the
downscaling and upscaling strategies: (a) single-input single-output (SISO)
for both operations, (b) SISO for downscaling and multi-input single-output
(MISO) for upscaling, and (c) multi-input multi-output (MIMO) for both
operations (the proposed method).

In this paper, we address the joint optimization of video downscaling and
upscaling as a combined task, which is referred to as video rescaling. This
task involves downscaling an HR video into a low-resolution (LR) one, followed
by upscaling the resulting LR video back to HR. Our aim is to optimize the HR
reconstruction quality while regularizing the LR video to offer comparable
visual quality to the bicubic-downscaled video for human perception. It is to
be noted that the rescaling task differs from the super-resolution task; at
inference time, the former has access to the HR video while the latter has no
such information.

One straightforward solution to video rescaling is to downscale an HR video by
predefined kernels and upscale the LR video with super-resolution methods [14,
17, 32, 26, 3, 6, 1, 23, 20, 10, 25, 31, 8, 15, 9]. With this solution, the
downscaling is operated independently of the upscaling although the upscaling
can be optimized for the chosen downscaling kernels. The commonly used
downscaling (e.g. bicubic) kernels suffer from losing the high-frequency
information [21] inherent in the HR video, thus creating a many-to-one mapping
between the HR and LR videos. Reconstructing the HR video by upscaling its LR
representation becomes an ill-posed problem. The independently-operated
downscaling misses the opportunity of optimizing the downscaled video to
mitigate the ill-posedness.

The idea of jointly optimizing downscaling and upscaling was first proposed
for image rescaling [11, 16, 22, 2]. It adds a new dimension of thinking to
the studies of learning specifically to upscale for a given downscaling method
[14, 17, 32, 26, 3, 6]. Recognizing the reciprocality of the downscaling and
upscaling operations, IRN [29] recently introduced a coupling layer-based
invertible model, which shows much improved HR reconstruction quality than the
non-invertible models.

These jointly optimized image-based solutions (Fig. 1(a)) are not ideal for
video rescaling. For example, a large number of prior works [1, 23, 20, 10,
25, 31, 8, 15, 9] for video upscaling have adopted the Multi-Input Single-
Output (MISO) strategy to reconstruct one HR frame from multiple LR frames
and/or previously reconstructed HR frames (Fig. 1(b)). They demonstrate the
potential for recovering the missing high-frequency component of a video frame
from temporal information. However, image-based solutions do not consider
temporal information. In addition, two issues remain widely open as (1) how
video downscaling and upscaling could be jointly optimized and (2) how
temporal information could be utilized in the joint optimization framework to
benefit both operations.

In this paper, we present two joint optimization approaches to video
rescaling: Long Short-Term Memory Video Rescaling Network (LSTM-VRN) and
Multi-Input Multi-Output Video Rescaling Network (MIMO-VRN). The LSTM-VRN
downscales an HR video frame-by-frame using a similar coupling architecture to
[29], but fuses multiple downscaled LR video frames via LSTM to estimate the
missing high-frequency component of an LR video frame for upscaling (Fig.
1(b)). LSTM-VRN shares similar downscaling and upscaling strategies to the
traditional video rescaling framework. In contrast, our MIMO-VRN introduces a
completely new paradigm by adopting the MIMO strategy for both video
downscaling and upscaling (Fig. 1(c)). We develop a group-of-frames-based
(GoF) coupling architecture that downscales multiple HR video frames
simultaneously, with their high-frequency components being estimated also
simultaneously in the upscaling process. Our contributions include the
following:

  * •

To the best of our knowledge, this work is the first attempt at jointly
optimizing video downscaling and upscaling with invertible coupling
architectures.

  * •

Our LSTM-VRN and MIMO-VRN outperform the image-based invertible model [29],
showing significantly improved HR reconstruction quality and offering LR
videos comparable to the bicubic-downscaled video in terms of visual quality.

  * •

Our MIMO-VRN is the first scheme to introduce the MIMO strategy for video
upscaling and downscaling, achieving the state-of-the-art performance.

##  2 Related Work

Figure 2: Taxonomy of the prior works on image/video rescaling. The SISO, MISO
and MIMO indicate the strategies (i.e. the input/output format) for
downscaling and upscaling. SISR and VSR stand for single image super-
resolution and video super-resolution, respectively. CAR [22] and IRN [29] are
joint optimization schemes for image rescaling.

This section surveys video rescaling methods, with a particular focus on their
downscaling and upscaling strategies. We regard the image-based rescaling
methods as possible solutions for video rescaling. Fig. 2 is a taxonomy of
these prior works.

###  2.1 Upscaling with Predefined Downscaling

The traditional image super-resolution [14, 17, 32, 26, 3, 6] or video super-
resolution [1, 23, 20, 10, 25, 31, 8, 15, 9] methods are candidate solutions
to video upscaling. The former is naturally a single-input single-output
(SISO) upscaling strategy, which generates one HR image from one LR image. The
latter usually involves more than one LR video frame in the upscaling process,
i.e. the MISO upscaling strategy, in order to leverage temporal information
for better HR reconstruction quality. Most of the approaches in this category
adopt a SISO downscaling strategy with a pre-defined kernel (e.g. bicubic)
chosen independently of the upscaling process. Therefore, they are unable to
adapt the downscaled images/videos to the upscaling.

###  2.2 Upscaling with Jointly Learned Downscaling

To mitigate the ill-posedness of the image upscaling task, some works learn
upscaling and downscaling jointly by encoder-decoder architectures [11, 16,
22, 2]. They turn the fixed downscaling method into a learnable model in order
to adapt the LR image to the upscaling process that is learned jointly. The
training objective usually requires the LR image to be also suitable for human
perception. Recently, IRN [29] introduces an invertible model [4, 5, 13] to
this joint optimization task. It is able to perform image downscaling and
upscaling by the same set of neural networks configured in the reciprocal
manner. It provides a means to model explicitly the missing high-frequency
information due to downscaling by a Gaussian noise.

Figure 3: The detailed downscaling operation of IRN [29]. The model performs
$\times 4$ downscaling with two downscaling modules, each of which comprises a
2-D Haar transform and eight coupling layers. Each downscaling module halves
the horizontal and vertical resolutions of the input image.

###  2.3 Invertible Rescaling Network

IRN [29] is an invertible model designed specifically for image rescaling. The
forward model of IRN comprises a 2-D Haar transform and eight coupling layers
[4, 5, 13], as shown in Fig. 3. By applying the 2-D Haar transform, an input
image $x\in\mathbb{R}^{C\times H\times W}$ is first decomposed into one low-
frequency band $y^{\prime}\in\mathbb{R}^{C\times\frac{H}{2}\times\frac{W}{2}}$
and three other high-frequency bands
$z^{\prime}\in\mathbb{R}^{3C\times\frac{H}{2}\times\frac{W}{2}}$. These two
components $y^{\prime},z^{\prime}$ are subsequently processed via the coupling
layers in a way that the output $y$ becomes a visually-pleasing LR image and
the $z$ encodes the complementary high-frequency information inherent in the
input HR image $x$. In theory, the inverse coupling layers can recover $x$
losslessly from $y$ and $z$ because the model is invertible. In practice, $z$
is unavailable for upscaling at inference time. The training of IRN requires
$z$ to follow a Gaussian distribution so that at inference time, a Gaussian
sample $\hat{z}$ can be drawn as a substitute for the missing high-frequency
component.

Although IRN achieves superior results on the image rescaling task, it is not
optimal for video rescaling. Essentially, IRN is an image-based method. This
work presents the first attempt at jointly optimizing video downscaling and
upscaling with an invertible coupling architecture (Fig. 3).

##  3 Proposed Method

(a) LSTM-VRN

(b) MIMO-VRN

Figure 4: Overview of the proposed LSTM-VRN and MIMO-VRN for video rescaling.
Both schemes involve an invertible network with coupling layers for video
downscaling and upscaling. In part (a), LSTM-VRN downscales every video frame
$x_{t}$ independently and forms a prediction $\hat{z}_{t}$ of the high-
frequency component $z_{t}$ from the LR video frames
$\\{\hat{y}_{i}\\}_{i=t-L}^{t+L}$ by a bi-directional LSTM that operates in a
sliding window manner. In part (b), MIMO-VRN downscales a group of HR video
frames $\\{x_{i}\\}_{i=t}^{t+g}$ into the LR video frames
$\\{\hat{y}_{i}\\}_{i=t}^{t+g}$ simultaneously. The upscaling is also done on
a group-by-group basis, with the high-frequency components
$\\{z_{i}\\}_{i=t}^{t+g}$ estimated from the $\\{\hat{y}_{i}\\}_{i=t}^{t+g}$
by a predictive module.

Given an HR video composed of $N$ video frames $\\{x_{t}\\}_{t=1}^{N}$, where
$x_{t}\in\mathbb{R}^{C\times H\times W}$, the video rescaling task involves
(1) downscaling every video frame $x_{t}$ to its LR counterpart
$y_{t}\in\mathbb{R}^{C\times\frac{H}{4}\times\frac{W}{4}}$, where the
quantized version $\hat{y}_{t}$ of which forms collectively an LR video
$\\{\hat{y}_{t}\\}_{t=1}^{N}$, and (2) upscaling the LR video to arrive at the
reconstructed HR video $\\{\hat{x}_{t}\\}_{t=1}^{N}$. Unlike most video super-
resolution tasks, which focus primarily on learning upscaling for a given
downscaling method, this work optimizes jointly the downscaling and upscaling
as a combined task. It has been shown in many traditional video super-
resolution works [1, 23, 20, 7, 24, 25, 10, 31, 9, 15, 8] that the extra
temporal information in videos allows the lost high-frequency component of a
video frame due to downscaling to be recovered to some extent. This work makes
the first attempt to explore how such temporal information could assist
downscaling in producing an LR video that can be upscaled to offer better
super-resolution quality in an end-to-end fashion. In a sense, our focus is on
both downscaling and upscaling. The objective is to minimize the distortion
between $\\{\hat{x}_{t}\\}_{t=1}^{N}$ and $\\{x_{t}\\}_{t=1}^{N}$ in such a
combined task while the LR video $\\{\hat{y}_{t}\\}_{t=1}^{N}$ is regularized
to offer comparable visual quality to the bicubic-downscaled video for human
perception. It is to be noted that the LR video is not meant to be exactly the
same as the bicubic-downscaled video since doing so may not lead to the
optimal downscaling and upscaling in our task.

The reciprocality of the downscaling and upscaling operations motivates us to
choose an invertible network for our task. With the superior performance of
coupling layer architectures in recovering high-frequency details of LR images
[29], we develop our downscaling and upscaling networks, especially for video,
using a similar invertible architecture (Sec. 2.3) as the basic building
block.

We propose two approaches, LSTM-VRN and MIMO-VRN, to configure or extend these
building blocks for joint learning of video downscaling and upscaling. Their
overall architectures are depicted in Fig. 4, with detailed operations given
in the following sections.

###  3.1 LSTM-based Video Rescaling Network

Like most video super-resolution techniques, the LSTM-VRN (Fig. 4(a)) adopts
the SISO strategy to downscale HR video frames $\\{x_{t}\\}_{t=1}^{N}$
individually to their LR ones $\\{\hat{y}_{t}\\}_{t=1}^{N}$ by the forward
model of the invertible network. The operation is followed by the MISO-based
upscaling, which departs from the idea of drawing an input-agnostic Gaussian
noise [29] for complementary high-frequency information. Specifically, we fuse
the current LR frame ${\hat{y}_{t}}$ and its neighbouring frames
$\\{\hat{y}_{t-i},\hat{y}_{t+i}\\}_{i=1}^{L}$ by a LSTM-based predictive
module to form an estimate $\hat{z}_{t}$ of the missing high-frequency
component $z_{t}$ at inference time. The resulting $\hat{z}_{t}$ is fed to the
inverse model together with the ${\hat{y}_{t}}$ for reconstructing the HR
video frame $\hat{x}_{t}$. The fact that $z_{t}$ needs to be estimated from
multiple LR frames $\\{\hat{y}_{i}\\}_{i=t-L}^{t+L}$ determines what
information should remain in the LR video to facilitate the prediction. This
connects the upscaling process tightly to the downscaling process, stressing
the importance of their joint optimization. In addition, we rely on the inter-
branch pathways of the coupling layer in the forward model to correlate
$z_{t}$ and $y_{t}$ in such a way that $z_{t}$ could be better predicted from
$\hat{y}_{t}$ and its neighbors $\\{\hat{y}_{t-i},\hat{y}_{t+i}\\}_{i=1}^{L}$.

The predictive module plays a key role in fusing information from
$\hat{y}_{t}$ and $\\{\hat{y}_{t-i},\hat{y}_{t+i}\\}_{i=1}^{L}$. We
incorporate Spatiotemporal-LSTM (ST-LSTM) [27] for propagating temporal
information in both forward and backward directions, in view of its recent
success in video extrapolation tasks. Eq. (1) details the forward mode of the
predictive module for time instance $t$:

$\displaystyle h^{f}_{t}$ $\displaystyle=ST\mbox{-}LSTM(f_{t-1},h^{f}_{t-1})$
(1) $\displaystyle h^{y}_{t}$ $\displaystyle=ResidualBlock(\hat{y}_{t})$
$\displaystyle a_{t}$ $\displaystyle=\sigma(W\otimes h^{y}_{t})$
$\displaystyle f_{t}$ $\displaystyle=(1-a_{t})\odot h^{f}_{t}+a_{t}\odot
h^{y}_{t}$

where $\sigma$ is a sigmoid function, $\otimes$ is the standard convolution,
and $\odot$ is Hadamard product. Note that an attention signal $a_{t}$ guided
by the the current LR frame $\hat{y}_{t}$ combines the temporally-propagated
hidden information $h^{f}_{t}$ and the features $h^{y}_{t}$ of $\hat{y}_{t}$
to yield the output $f_{t}$. As Fig. 4(a) shows, the forward propagated
$f_{t}$ is further combined with the backward propagated $b_{t}$ to predict
$\hat{z}_{t}$ through a 1x1 convolution.

For upscaling every LR video frame $\hat{y}_{t}$, the proposed predictive
module works in a sliding-window manner with a window size of $2L+1$. That is,
the forward (respectively, backward) ST-LSTM always starts with a reset state
0 when accepting the input $\hat{y}_{t-L}$ (respectively, $\hat{y}_{t+L}$).
This design choice is out of generalization and buffering considerations. We
avoid running a long ST-LSTM at inference time because the training videos are
rather short. Moreover, the backward ST-LSTM introduces delay and buffering
requirements.

Finally, we note in passing that LSTM-VRN exploits temporal information across
LR video frames only for upscaling while its downscaling is still a SISO-based
scheme, which does not take advantage of temporal information in HR video
frames for downscaling.

###  3.2 MIMO-based Video Rescaling Network

Our MIMO-VRN (Fig. 4(b)) is a new attempt that adopts a MIMO strategy for both
upscaling and downscaling, making explicit use of temporal information in
these operations. Here, we propose a new basic processing unit, called Group
of Frames (GoF). To begin with, the HR input video $\\{x_{t}\\}_{t=1}^{N}$ is
decomposed into non-overlapping groups of frames, with each group including
$g$ frames, namely $\\{x_{t}\\}_{t=1}^{g},\\{x_{t}\\}_{t=g+1}^{2g},\ldots$.
The downscaling proceeds on a group-by-group basis; each GoF is downscaled
independently of each other. Within a GoF, every HR video frame
$x_{t}\in\mathbb{R}^{C\times H\times W}$ is first transformed individually
using 2-D Haar Wavelet, to arrive at its low-frequency
$y^{\prime}_{t}\in\mathbb{R}^{C\times\frac{H}{2}\times\frac{W}{2}}$ and high-
frequency $z^{\prime}_{t}\in\mathbb{R}^{3C\times\frac{H}{2}\times\frac{W}{2}}$
components. We then group the low-frequency components
$\\{y^{\prime}_{i}\\}_{i=t}^{t+g}$ in a GoF as one group-type input
$\mathcal{Y}^{\prime}_{t}\in\mathbb{R}^{gC\times\frac{H}{2}\times\frac{W}{2}}$
to the coupling layers (i.e. replacing $y^{\prime}$ in Fig. 3 with
$\mathcal{Y}^{\prime}_{t}$) and the remaining high-frequency components
$\\{z^{\prime}_{i}\\}_{i=t}^{t+g}$ as the other group-type input
$\mathcal{Z}^{\prime}_{t}\in\mathbb{R}^{3gC\times\frac{H}{2}\times\frac{W}{2}}$
(i.e. replacing $z^{\prime}$ in Fig. 3 with $\mathcal{Z}^{\prime}_{t}$).
Because each group-type input contains information from multiple video frames,
the coupling layers are able to utilize temporal information inherent in one
group-type input to update the other. With two downscaling modules, the
results are a group of quantized LR frames
$\hat{\mathcal{Y}}_{t}=\\{\hat{y}_{i}\\}_{i=t}^{t+g}$ and the group high-
frequency component $\mathcal{Z}_{t}=\\{z_{i}\\}_{i=t}^{t+g}$. It is worth
noting that due to the nature of group-based coupling, there is no one-to-one
correspondence between the signals in
$\hat{\mathcal{Y}}_{t}\in\mathbb{R}^{gC\times\frac{H}{4}\times\frac{W}{4}}$
and $\mathcal{Z}_{t}\in\mathbb{R}^{3gC\times\frac{H}{4}\times\frac{W}{4}}$.

The upscaling proceeds also on a group-by-group basis, with the group size $g$
and the group formation fully aligned with those used for downscaling. As
depicted in Fig. 4(b), we employ a residual block-based predictive module to
form a prediction of the missing high-frequency components
$\\{z_{i}\\}_{i=t}^{t+g}$ from the corresponding group of LR frames
$\\{\hat{y}_{i}\\}_{i=t}^{t+g}$. Similar to the notion of the group-type
inputs for downscaling, the LR frames $\\{\hat{y}_{i}\\}_{i=t}^{t+g}$ and the
estimated high-frequency components $\\{\hat{z}_{i}\\}_{i=t}^{t+g}$ comprise
respectively the two group-type inputs $\hat{\mathcal{Y}}_{t}$ and
$\hat{\mathcal{Z}}_{t}$ to the invertible network operated in inverse mode.
With this MIMO-based upscaling, a group of HR frames
$\\{\hat{x}_{i}\\}_{i=t}^{t+g}$ are reconstructed simultaneously.

###  3.3 Training Objectives

LSTM-VRN. The training of LSTM-VRN involves two loss functions to reflect our
objectives. First, to ensure that the LR video $\\{\hat{y}_{t}\\}_{t=1}^{N}$
is visually pleasing, we follow common practice to require that
$\\{\hat{y}_{t}\\}_{t=1}^{N}$ have similar visual quality to the bicubic-
downscaled video $\\{x^{bic}_{t}\\}_{t=1}^{N}$; to this end, we define the LR
loss as

$\mathcal{L}_{LR}=\frac{1}{N}\sum^{N}_{t=1}\|x^{bic}_{t}-\hat{y}_{t}\|^{2}.$
(2)

Second, to maximize the HR reconstruction quality, we minimize the Charbonnier
loss [14] between the original HR video $\\{x_{t}\\}_{t=1}^{N}$ and its
reconstructed version $\\{\hat{x}_{t}\\}_{t=1}^{N}$ subject to downscaling and
upscaling:

$\mathcal{L}_{HR}=\frac{1}{N}\sum^{N}_{t=1}\sqrt{\|x_{t}-\hat{x}_{t}\|^{2}+\epsilon^{2}},$
(3)

where $\epsilon$ is set to $1\times 10^{-3}$. The total loss is
$\mathcal{L}_{total}=\mathcal{L}_{HR}+\lambda\mathcal{L}_{LR}$, where
$\lambda$ is a hyper-parameter used to trade-off between the quality of the LR
and HR videos.

MIMO-VRN. The training of MIMO-VRN shares the same $\mathcal{L}_{LR}$ and
$\mathcal{L}_{HR}$ losses as LSTM-VRN because they have common optimization
objectives. We however notice that MIMO-VRN tends to have uneven HR
reconstruction quality over video frames in a GoF (Sec. 4.4). To mitigate the
quality fluctuation in a GoF, we additionally introduce the following center
loss for MIMO-VRN:

$\mathcal{L}_{center}=\frac{1}{M\times
g}\sum_{m=1}^{M}\sum^{mg}_{t=(m-1)g+1}\left|\|x_{t}-\hat{x}_{t}\|^{2}-c_{m}\right|,$
(4)

where $g$ is the group size,
$c_{m}=\sum^{mg}_{t=(m-1)g+1}\|x_{t}-\hat{x}_{t}\|^{2}/g$ denotes the average
HR reconstruction error in a GoF, and $M$ is the number of GoF’s in a
sequence. Eq. (4) encourages the HR reconstruction error of every video frame
in a GoF to approximate the average level $c_{m}$.

##  4 Experimental Results

###  4.1 Setup

Datasets. For a fair comparison, we follow the common test protocol to train
our models on Vimeo-90K dataset [30]. It has 91,701 video sequences, each is 7
frames long. Among them, 64,612 sequences are for training and 7,824 are for
test. Each sequence has a fixed spatial resolution of 448 $\times$ 256\. The
performance evaluation is done on two standard test datasets, Vimeo-90K-T and
Vid4 [18]. Vid4 includes 4 video clips, each having around 40 frames.

Table 1: PSNR-Y / SSIM-Y comparison on Vid4 for $\times 4$ upscaling. ’$\dagger$’ represents the model adopting the joint optimization for downscaling and upscaling. Red, green, and blue indicate the best, the second best, and the third best performance, respectively. Downscale | Upscale | Method | Calendar | City | Foliage | Walk | Average
---|---|---|---|---|---|---|---
SISO | SISO | DRN-L [6] | 22.47 / 0.7289 | 26.25 / 0.7011 | 24.88 / 0.6681 | 28.84 / 0.8752 | 25.61 / 0.7433
CAR† [22] | 24.48 / 0.8143 | 30.19 / 0.8444 | 26.98 / 0.7841 | 31.59 / 0.9250 | 28.28 / 0.8421
IRN† [29] | 26.62 / 0.8850 | 33.48 / 0.9337 | 29.71 / 0.8871 | 35.36 / 0.9696 | 31.29 / 0.9188
MISO | DUF [10] | 24.04 / 0.8110 | 28.27 / 0.8313 | 26.41 / 0.7709 | 30.60 / 0.9141 | 27.33 / 0.8318
EDVR-L [25] | 24.05 / 0.8147 | 28.00 / 0.8122 | 26.34 / 0.7635 | 31.02 / 0.9152 | 27.35 / 0.8264
PFNL [31] | 24.37 / 0.8246 | 28.09 / 0.8385 | 26.51 / 0.7768 | 30.65 / 0.9135 | 27.40 / 0.8384
TGA [9] | 24.47 / 0.8286 | 28.37 / 0.8419 | 26.59 / 0.7793 | 30.96 / 0.9181 | 27.59 / 0.8419
RSDN [8] | 24.60 / 0.8355 | 29.20 / 0.8527 | 26.84 / 0.7931 | 31.04 / 0.9210 | 27.92 / 0.8505
LSTM-VRN† | 27.31 / 0.9039 | 34.36 / 0.9482 | 31.13 / 0.9213 | 36.18 / 0.9742 | 32.24 / 0.9369
MIMO | MIMO | MIMO-VRN† | 29.23 / 0.9389 | 35.49 / 0.9573 | 33.25 / 0.9535 | 37.17 / 0.9812 | 33.79 / 0.9577
MIMO-VRN-C† | 28.83 / 0.9322 | 35.13 / 0.9544 | 32.72 / 0.9476 | 36.93 / 0.9808 | 33.40 / 0.9537

Implementation and Training Details. Our proposed models adopt the settings
from IRN [29], which consists of two downscaling modules (Fig. 3). Each module
is composed of one 2-D Haar transform and eight coupling layers. Both LSTM-VRN
and MIMO-VRN have eight predictive modules (Fig. 4) replicated and stacked for
a better prediction of the missing high-frequency component. The sliding
window size for LSTM-VRN is set to 7, which includes the current LR video
frame together with 6 neighbouring LR frames (3 from the past and 3 from the
future). The GoF size $g$ for MIMO-VRN is set to 5. For data augmentation, we
randomly crop training videos to 144 $\times$ 144 as HR inputs and use their
bicubic-downscaled versions (of size 36 $\times$ 36) as LR ground-truths. We
also apply random horizontal and vertical flipping. LSTM-VRN and MIMO-VRN
share the same LR and HR training objectives (Eq. (2) and Eq. (3)), with the
$\lambda$ for $\mathcal{L}_{LR}$ set to 64. The training of MIMO-VRN
additionally includes the center loss (Eq. (4)), the hyper-parameter of which
is chosen to be 16. We use Adam optimizer [12], with $\beta_{1}=0.9$,
$\beta_{2}=0.5$ and a batch size of 16. The weight decay is set to $1\times
10^{-12}$. We use an initial learning rate of $1\times 10^{-4}$, which is
decreased by half for every $30k$ iterations. Our code is available online
111https://ding3820.github.io/MIMO-VRN/.

Table 2: PSNR-Y / SSIM-Y comparison on Vimeo-90K-T for $\times 4$ upscaling. ’$\dagger$’ represents the model adopting the joint optimization for downscaling and upscaling. Red, green, and blue indicate the best, the second best, and the third best performance, respectively. Downscale | Upscale | Method | Average
---|---|---|---
SISO | SISO | DRN-L [6] | 35.63 / 0.9262
CAR† [22] | 37.69 / 0.9493
IRN† [29] | 40.83 / 0.9734
MISO | DUF [10] | 36.37 / 0.9387
EDVR-L [25] | 37.63 / 0.9487
TGA [9] | 37.59 / 0.9516
RSDN [8] | 37.23 / 0.9471
LSTM-VRN† |  41.42 / 0.9764
MIMO | MIMO | MIMO-VRN† |  43.26 / 0.9846
MIMO-VRN-C† |  42.53 / 0.9820

Baselines. We include three categories of baselines for comparison: (1) SISO-
down-SISO-up with predefined downscaling kernels (e.g. DRN-L [6]), (2) SISO-
down-SISO-up with jointly optimized downscaling and upscaling (e.g. CAR [22]
and IRN [29]), and (3) SISO-down-MISO-up with predefined downscaling kernels
(e.g. DUF [10], EDVR-L [25], PFNL [31], TGA [9], and RSDN [8]). The first two
categories perform video downscaling and upscaling on a frame-by-frame basis.
The third category includes the state-of-the-art video super-resolution
methods, where the predefined downscaling is done frame-by-frame and the
learned upscaling is MISO-based. The predefined downscaling uses the bicubic
interpolation method. It is to be noted that the methods adopting the learned
downscaling perform upscaling based on their respective LR videos, which would
not be the same as the bicubic-downscaled videos. The results for the methods
in categories (1) and (2) are produced using the pre-trained models released
by the authors. Those in category (3) are taken from the papers since these
baselines share exactly the same setting as ours. We report results for a
downscaling/upscaling factor of 4 only, following the common setting for video
rescaling.

Metrics. For quantitative comparison, we adopt the standard test protocol in
the super-resolution tasks to evaluate Peak Signal-to-Noise Ratio (PSNR) and
Structural Similarity Index (SSIM) [28] on the Y channel, denoted respectively
by PSNR-Y and SSIM-Y.

Figure 5: Sample LR video frames from Vid4. Our models show comparable visual
quality to the bicubic method.

###  4.2 Comparison of Quantitative Results

Tables 1 and 2 report the PSNR-Y and SSIM-Y results of the reconstructed HR
videos on Vid4 and Vimeo-90K-T. Table 3 summarizes the results for the
downscaled videos. The following observations are immediate:

(1) Optimizing jointly video downscaling and upscaling improves the HR
reconstruction quality. This is confirmed by the fact that LSTM-VRN achieves
considerably higher PSNR-Y (32.24dB on Vid4 and 41.42dB on Vimeo-90K-T) than
the baselines with video super-resolution methods for upscaling (27.33-27.92dB
on Vid4 and 36.37-37.59dB on Vimeo-90K-T) [25, 10, 31, 9, 8], which adopt the
same SISO-down-MSIO-up strategy yet with a predefined downscaling kernel. We
note that the image-based joint optimization schemes, e.g. IRN [29] and CAR
[22], achieve better HR reconstruction quality than the traditional video-
based baselines, even without using temporal information for upscaling. The
superior performance of joint optimization schemes is attributed to the fact
that they can better embed HR information in LR frames for upscaling.

(2) Incorporating temporal information in the LR video improves further on the
HR reconstruction quality. The result is evidenced by the 0.95dB and 0.59dB
PSNR-Y gains of LSTM-VRN over IRN [29] on Vid4 and Vimeo-90K-T. Both share a
similar invertible network for downscaling, but our LSTM-VRN additionally
leverages information from multiple LR video frames to predict the high-
frequency component of a video frame during upscaling.

(3) MIMO-VRN achieves the best PSNR-Y/SSIM-Y results. It outperforms LSTM-VRN
by 1.55dB and 1.84dB in PSNR-Y on Vid4 and Vimeo-90K-T, respectively, while
LSTM-VRN already shows a significant improvement over the other baselines. The
inclusion of the center loss (see MIMO-VRN-C) causes a modest decrease in
PSNR-Y/SSIM-Y but helps to alleviate the quality fluctuation in both the
resulting LR and HR videos (Sec. 4.4). These results highlight the benefits of
incorporating temporal information into both downscaling and upscaling in an
end-to-end optimized manner.

(4) Both LSTM-VRN and MIMO-VRN produce visually-pleasing LR videos. Table 3
shows that the LR videos produced by our models have a PSNR-Y of more than
40dB when compared against the bicubic-downscaled videos. This together with
the SSIM-Y results suggests that they are visually comparable to the bicubic-
downscaled videos, as is also confirmed by the subjective quality comparison
in Fig. 5 and the supplementary document.

Figure 6: Qualitative comparison on Vid4 for 4$\times$ upscaling. Zoom in for
better visualization.

###  4.3 Comparison of Qualitative Results

Figs. 6 presents a qualitative comparison on Vid4. As shown, our models
produce higher-quality HR video frames with much sharper edges and finer
details. The other methods show blurry image quality and fail to recover image
details. From Fig. 5, our downscaling models produce visually comparable
results to the bicubic downscaling method, which indicates the visually-
pleasing property of our LR videos. The reader is referred to our project page
1 for more results.

Table 3: PSNR-Y and SSIM-Y results measured between the $\times 4$ downscaled LR videos and the bicubic-downscaled videos. Method | Vid4 | Vimeo-90K-T
---|---|---
IRN [29] | 40.77 / 0.9908 | 46.24 / 0.9956
LSTM-VRN | 42.36 / 0.9940 | 47.14 / 0.9968
MIMO-VRN | 45.05 / 0.9965 | 49.11 / 0.9975
MIMO-VRN-C | 45.51 / 0.9969 | 49.34 / 0.9976

###  4.4 Ablation Experiments

Temporal Propagation Methods in LSTM-VRN. Table 4 presents results for three
temporal propagation schemes in LSTM-VRN. The first runs LSTM in forward
direction without reset. The second and the third implement the proposed
method with uni- or bi-directional propagation, respectively. We see that the
sliding window-based reset is advantageous to the HR reconstruction quality.
This may be attributed to the fact that the training videos in Vimeo-90K are
rather short. When trained on Vimeo-90K, the first variant may not generalize
well to unseen long videos in Vid4. As expected, with the access to both the
past and future LR frames, the bi-directional propagation performs better than
the uni-directional one (i.e. Fig. 4(a) without the backward path).

Table 4: Ablation study of the propagation methods for LSTM-VRN. Results are reported on Vid4. Sliding Window | Bi-directional | PSNR-Y
---|---|---
|  | 31.16
$\surd$ |  | 31.53
$\surd$ | $\surd$ | 32.24
Table 5: PSNR-Y of different GoF sizes on Vid4. IRN_Ret is the re-trained IRN with Vimeo-90K, as compared to IRN, the pre-trained model from [29]. Method | HR | LR
---|---|---
IRN [29] | 31.29 | 41.13
IRN_Ret | 30.72 | 45.06
GoF1 | 30.69 | 44.38
GoF3 | 33.61 | 43.85
GoF5 | 33.79 | 45.05
GoF7 | 33.45 | 45.13

GoF Size. Table 5 studies the effect of the GoF size on MIMO-VRN’s
performance. The setting GoF1 reduces to the SISO-up-SISO-down method, which
is similar to IRN [29] except that it introduces a prediction of the high-
frequency component from the LR video frame. For a fair comparison, we re-
train IRN [29] on Vimeo-90K and denote the re-trained model by IRN_Ret. Note
that the pre-trained IRN [29] performs better than IRN_Ret since it is trained
on a different (image-based) dataset. We see that GoF1 and IRN_Ret show
comparable performance, especially on the HR videos. This suggests that
without additional temporal information, the prediction of the high-frequency
component from the LR video is ineffective. However, increasing the GoF size,
which involves more temporal information in downscaling and upscaling,
improves the quality of the HR video significantly. GoF5 is seen to be the
best setting.

(a) Reconstructed HR video

(b) Downscaled LR video

Figure 7: The impact of the center loss on the quality of the HR and LR videos. The per-frame PSNR-Y is visualized as a function of frame indices. The GoF size is 5. MIMO-VRN: no center loss. HR: the center loss imposed on the HR video only. LR: the center loss imposed on the LR video only. HR&LR: the center loss imposed on both the HR and LR videos. Table 6: PSNR-Y of MIMO-VRN with and without the center loss on Vid4. The mean absolute deviation (MAD) indicates the average absolute deviation of the per-frame PSNR-Y from the GoF mean. Center loss | PSNR-Y | MAD
---|---|---
HR | LR | HR | LR | HR | LR
|  | 33.79 | 45.05 | 0.88 | 0.55
$\surd$ |  | 33.40 | 45.54 | 0.28 | 0.63
| $\surd$ | 33.55 | 42.42 | 0.86 | 0.38
$\surd$ | $\surd$ | 33.13 | 43.32 | 0.31 | 0.29

Center Loss. Fig. 7 visualizes the PSNR-Y of the HR and LR videos produced by
MIMO-VRN as functions of time. Without the center loss (see MIMO-VRN), the
PSNR-Y of both the HR and LR videos fluctuates periodically by as much as 2dB.
Observe that the crest points of the HR video occur roughly at the GoF centers
while the trough points are at the GoF boundaries. Table 6 performs an
ablation study of how this center loss would affect the HR and/or LR videos
when it is imposed on these videos. We observe that introducing the center
loss largely mitigates the quality fluctuation in the corresponding HR and/or
LR video (see the MAD results in Table 6 and Fig. 7). It however degrades the
HR and/or LR quality in terms of PSNR-Y, as compared to the case without the
loss. We make the choice of imposing the center loss on the HR video only for
two reasons. First, this leads to a minimal impact on the HR reconstruction
quality. The second is that the quality fluctuation in the LR video is less
problematic in terms of subjective quality because the PSNR-Y measured against
the bicubic-downscaled video is way above 40dB. On closer visual inspection,
these LR videos hardly show any artifacts in the temporal dimension.

###  4.5 Complexity-performance Trade-offs

LSTM-VRN and MIMO-VRN present different complexity-performance trade-offs. (1)
LSTM-VRN is relatively lightweight, having 9M network parameters as compared
to 19M with MIMO-VRN. (2) LSTM-VRN does not require additional buffering/delay
and storage for downscaling as is necessary for MIMO-VRN. (3) MIMO-VRN has
better LR/HR quality while LSTM-VRN has more consistent LR/HR quality
temporally. They use depends on the complexity constraints and performance
requirements of the application.

##  5 Conclusion

This work presents two joint optimization approaches to video rescaling. Both
incorporate an invertible network with coupling layer architectures to model
explicitly the high-frequency component inherent in the HR video. While our
LSTM-VRN shows that the temporal information in the LR video can be utilized
to good advantage for better upscaling, our MIMO-VRN demonstrates that the
GoF-based rescaling is able to make full use of temporal information to
benefit both upscaling and downscaling. Our models demonstrate superior
quantitative and qualitative performance to the image-based invertible model.
They outperform, by a significant margin, the video rescaling framework
without joint optimization.

#### Acknowledgements.

This work is supported by Qualcomm technologies, Inc. (NAT-439543), Ministry
of Science and Technology, Taiwan (109-2634-F-009-020) and National Center for
High-performance Computing, Taiwan.

## References

  * [1] Jose Caballero, Christian Ledig, Andrew Aitken, Alejandro Acosta, Johannes Totz, Zehan Wang, and Wenzhe Shi.  Real-time video super-resolution with spatio-temporal networks and motion compensation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
  * [2] Yuzhao Chen, Xi Xiao, Tao Dai, and Shu-Tao Xia.  Hrnet: Hamiltonian rescaling network for image downscaling.  In IEEE International Conference on Image Processing (ICIP), 2020\.
  * [3] Tao Dai, Jianrui Cai, Yongbing Zhang, Shu-Tao Xia, and Lei Zhang.  Second-order attention network for single image super-resolution.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [4] Laurent Dinh, David Krueger, and Yoshua Bengio.  Nice: Non-linear independent components estimation.  In Proceedings of International Conference on Learning Representations (ICLR), 2015.
  * [5] Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio.  Density estimation using real nvp.  In Proceedings of International Conference on Learning Representations (ICLR), 2017.
  * [6] Yong Guo, Jian Chen, Jingdong Wang, Qi Chen, Jiezhang Cao, Zeshuai Deng, Yanwu Xu, and Mingkui Tan.  Closed-loop matters: Dual regression networks for single image super-resolution.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [7] Muhammad Haris, Gregory Shakhnarovich, and Norimichi Ukita.  Recurrent back-projection network for video super-resolution.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [8] Takashi Isobe, Xu Jia, Shuhang Gu, Songjiang Li, Shengjin Wang, and Qi Tian.  Video super-resolution with recurrent structure-detail network.  In Proceedings of European Conference on Computer Vision (ECCV), 2020.
  * [9] Takashi Isobe, Songjiang Li, Xu Jia, Shanxin Yuan, Gregory Slabaugh, Chunjing Xu, Ya-Li Li, Shengjin Wang, and Qi Tian.  Video super-resolution with temporal group attention.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [10] Younghyun Jo, Seoung Wug Oh, Jaeyeon Kang, and Seon Joo Kim.  Deep video super-resolution network using dynamic upsampling filters without explicit motion compensation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [11] Heewon Kim, Myungsub Choi, Bee Lim, and Kyoung Mu Lee.  Task-aware image downscaling.  In Proceedings of European Conference on Computer Vision (ECCV), 2018.
  * [12] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In Proceedings of International Conference on Learning Representations (ICLR), 2015.
  * [13] Durk P Kingma and Prafulla Dhariwal.  Glow: Generative flow with invertible 1x1 convolutions.  In Advances in Neural Information Processing Systems (NIPS), 2018\.
  * [14] Wei-Sheng Lai, Jia-Bin Huang, Narendra Ahuja, and Ming-Hsuan Yang.  Deep laplacian pyramid networks for fast and accurate super-resolution.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
  * [15] Wenbo Li, Xin Tao, Taian Guo, Lu Qi, Jiangbo Lu, and Jiaya Jia.  Mucan: Multi-correspondence aggregation network for video super-resolution.  In Proceedings of European Conference on Computer Vision (ECCV), 2020.
  * [16] Yue Li, Dong Liu, Houqiang Li, Li Li, Zhu Li, and Feng Wu.  Learning a convolutional neural network for image compact-resolution.  IEEE Transactions on Image Processing (TIP), 2018.
  * [17] Bee Lim, Sanghyun Son, Heewon Kim, Seungjun Nah, and Kyoung Mu Lee.  Enhanced deep residual networks for single image super-resolution.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, 2017.
  * [18] Ce Liu and Deqing Sun.  On bayesian adaptive video super resolution.  IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2013.
  * [19] R. Rassool.  Vmaf reproducibility: Validating a perceptual practical video quality metric.  In 2017 IEEE International Symposium on Broadband Multimedia Systems and Broadcasting (BMSB), 2017.
  * [20] Mehdi SM Sajjadi, Raviteja Vemulapalli, and Matthew Brown.  Frame-recurrent video super-resolution.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [21] Claude Elwood Shannon.  Communication in the presence of noise.  Proceedings of the IRE, 1949.
  * [22] Wanjie Sun and Zhenzhong Chen.  Learned image downscaling for upscaling using content adaptive resampler.  IEEE Transactions on Image Processing (TIP), 2020.
  * [23] Xin Tao, Hongyun Gao, Renjie Liao, Jue Wang, and Jiaya Jia.  Detail-revealing deep video super-resolution.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
  * [24] Yapeng Tian, Yulun Zhang, Yun Fu, and Chenliang Xu.  Tdan: Temporally-deformable alignment network for video super-resolution.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
  * [25] Xintao Wang, Kelvin CK Chan, Ke Yu, Chao Dong, and Chen Change Loy.  Edvr: Video restoration with enhanced deformable convolutional networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, 2019.
  * [26] Xintao Wang, Ke Yu, Shixiang Wu, Jinjin Gu, Yihao Liu, Chao Dong, Yu Qiao, and Chen Change Loy.  Esrgan: Enhanced super-resolution generative adversarial networks.  In The European Conference on Computer Vision Workshops, 2018.
  * [27] Yunbo Wang, Mingsheng Long, Jianmin Wang, Zhifeng Gao, and S Yu Philip.  Predrnn: Recurrent neural networks for predictive learning using spatiotemporal lstms.  In Advances in Neural Information Processing Systems (NIPS), 2017\.
  * [28] Zhou Wang, Alan C Bovik, Hamid R Sheikh, and Eero P Simoncelli.  Image quality assessment: from error visibility to structural similarity.  IEEE Transactions on Image Processing (TIP), 2004.
  * [29] Mingqing Xiao, Shuxin Zheng, Chang Liu, Yaolong Wang, Di He, Guolin Ke, Jiang Bian, Zhouchen Lin, and Tie-Yan Liu.  Invertible image rescaling.  In Proceedings of European Conference on Computer Vision (ECCV), 2020.
  * [30] Tianfan Xue, Baian Chen, Jiajun Wu, Donglai Wei, and William T Freeman.  Video enhancement with task-oriented flow.  International Journal of Computer Vision (IJCV), 2019.
  * [31] Peng Yi, Zhongyuan Wang, Kui Jiang, Junjun Jiang, and Jiayi Ma.  Progressive fusion video super-resolution network via exploiting non-local spatio-temporal correlations.  In Proceedings of IEEE International Conference on Computer Vision (ICCV), 2019.
  * [32] Yulun Zhang, Kunpeng Li, Kai Li, Lichen Wang, Bineng Zhong, and Yun Fu.  Image super-resolution using very deep residual channel attention networks.  In Proceedings of European Conference on Computer Vision (ECCV), 2018.

Appendix

This supplementary document provides additional results to validate the
proposed methods. These include (1) quantitative results based on the Video
Multi-Method Assessment Fusion (VMAF) metric [19], a video quality metric that
is shown to correlate highly with human perception; (2) an examination of
temporal consistency on the downscaled and upscaled videos following the
method in RSDN [8]; (3) an ablation study of the predictive module; and (4)
more qualitative results of the downscaled and upscaled videos.

##  Appendix A Quantitative results based on VMAF

This section presents quantitative results for upscaled and downscaled videos
in Vid4 based on the Video Multi-Method Assessment Fusion (VMAF) [19] metric.
VMAF is an objective video quality metric that is shown to correlate highly
with human perception. It accepts as inputs a reference video and a distorted
video. Its output is a score between 0 and 100. The higher the VMAF score, the
more closely the two input videos match each other. Compared in Table 7 are
the VMAF scores of the reconstructed high-resolution (HR) videos produced by a
few baselines (whose code is available) and our schemes. The reference videos
are the original HR videos. Likewise, Table 8 shows the results for the
downscaled videos, where the reference videos are the bicubic-downscaled
videos.

From Table 7, we observe that our LSTM-VRN, MIMO-VRN and MIMO-VRN-C outperform
IRN [29] (image-based joint optimization scheme) consistently. As compared
with EDVR-L [25], a traditional video super-resolution approach, the proposed
methods show significantly improved VMAF scores. These observations are in
line with the PSNR/SSIM results reported in Table 1 of the main paper. A
similar observation can be made regarding the results of the downscaled LR
videos in Table 8, which agrees with the PSNR/SSIM results in Table 3 of the
main paper. Remarkably, all three proposed methods have VMAF scores very close
to 100, suggesting that their LR videos are visually similar to bicubic-
downscaled videos.

Table 7: Comparison of VMAF scores for $\times 4$ upscaled HR videos on Vid4. The reference videos are the original HR videos. The higher the VMAP scores, the better the HR reconstruction quality. Red and green indicate the best and the second best performance, respectively. Method | Calendar | City | Foliage | Walk | Average
---|---|---|---|---|---
EDVR-L [25] | 64.11 | 47.22 | 77.12 | 89.86 | 69.58
IRN [29] | 77.85 | 80.80 | 89.83 | 97.01 | 86.37
LSTM-VRN | 78.03 | 85.16 | 91.14 | 97.81 | 88.04
MIMO-VRN | 81.99 | 87.35 | 95.31 | 98.57 | 90.81
MIMO-VRN-C | 80.44 | 85.47 | 94.24 | 98.42 | 89.64
Table 8: Comparison of VMAF scores for $\times 4$ downscaled LR videos on Vid4. The reference videos are generated by the bicublic downscaling method. The higher the VMAP scores, the more closely the LR videos resemble the bicubic-downscaled ones. Red and green indicate the best and the second best performance, respectively. Method | Calendar | City | Foliage | Walk | Average
---|---|---|---|---|---
IRN [29] | 94.18 | 94.92 | 95.38 | 97.82 | 95.55
LSTM-VRN | 95.86 | 95.31 | 96.52 | 99.47 | 96.79
MIMO-VRN | 97.37 | 96.84 | 97.88 | 99.83 | 97.98
MIMO-VRN-C | 97.94 | 97.17 | 98.34 | 99.87 | 98.33
Table 9: Ablation study of the predictive module. IRN_Ret is trained using the same dataset as LSTM-VRN. MIMO-VRN-C-Zero is an implementation of MIMO-VRN-C without the predictive module. All the presented results are evaluated on Vid4 and they show that the proposed predictive module can improve the quality of reconstructed HR videos. Method | Predictive Module | HR (PSNR-Y / SSIM-Y / VMAF)
---|---|---
IRN_Ret |  | 30.72 / 0.9087 / 86.37
LSTM-VRN | $\surd$ | 32.24 / 0.9369 / 88.04
MIMO-VRN-C-Zero |  | 33.04 / 0.9575 / 89.00
MIMO-VRN-C | $\surd$ | 33.40 / 0.9609 / 89.64

##  Appendix B Temporal consistency

In this section, the temporal consistency of the downscaled and upscaled
videos is examined. We follow RSDN [8] to extract a row or a column of pixels
at the co-located positions in consecutive video frames. We then stitch
vertically (or horizontally) these extracted rows (or columns) of pixels to
form an image, in order to visualize their variations in the temporal
dimension. From Fig. 8, we are not aware of any noticeable inconsistency
across reconstructed HR video frames. Moreover, the resulting images of our
methods resemble closely the ground-truths.

In Fig. 9, IRN [29] and LSTM-VRN result in slight temporal inconsistency in
some areas of the low-resolution (LR) videos, particularly the Calendar and
City sequences. This is evidenced by the aliasing artifact especially appeared
on the alphabet of Calendar sequence and the building of City sequence.
Nevertheless, such inconsistency does not appear in the LR videos produced by
MIMO-VRN and MIMO-VRN-C.

##  Appendix C The effectiveness of the predictive module

Table 9 provides quantitative results to justify the effectiveness of the
proposed predictive module. Recall that the predictive module forms a
prediction $\hat{z}$ of the missing high-frequency component $z$ from the LR
video frames $\hat{y}$. This new feature distinguishes our schemes from IRN
[29], the image-based joint optimization scheme, which uses a Gaussian noise
for $\hat{z}$. The upper section of Table 9 compares the results of LSTM-VRN
with IRN_Ret (the re-trained IRN that uses the same training dataset as LSTM-
VRN), validating that the predictive module is effective for reconstructing
better HR videos. The lower section of Table 9 conducts the same analysis for
MIMO-VRN-C, where we replace $\hat{z}$ produced by the predictive module with
a fixed zero tensor, a scheme termed MIMO-VRN-C-Zero. MIMO-VRN-C-Zero is
trained in the same way as MIMO-VRN-C. We see that the predictive module is
still effective, even though the gain is less significant than the case in
LSTM-VRN.

##  Appendix D More qualitative results

Figs. 10 and 11 provide more qualitative results, comparing the reconstructed
HR videos of different models. They again suggest that our models can recover
fine details and sharp edges.

Fig. 12 presents a frame-by-frame qualitative comparison between MIMO-VRN and
MIMO-VRN-C, with a GoF size of 5. MIMO-VRN-C comes with an additional center
loss to ensure temporal consistency. It is seen that both MIMO-VRN and MIMO-
VRN-C can successfully reconstruct image details. Comparing MIMO-VRN with
MIMO-VRN-C, we are not aware of any significant quality variation in the
temporal dimension, even though Fig. 7 of the main paper suggests that the HR
quality of MIMO-VRN may fluctuate more significantly than MIMO-VRN-C. Fig. 13
displays more LR video frames from Vid4, showing that our models offer
comparable visual quality to the bicubic-downscaled videos.

Figure 8: Visualization of temporal consistency across the reconstructed HR
video frames. The images shown are formed by vertically (or horizontally)
stitching rows (or columns) of pixels extracted separately from consecutive
video frames at co-located positions (indicated by the red lines).

Figure 9: Visualization of temporal consistency across the downscaled LR video
frames. The images shown are formed by vertically (or horizontally) stitching
rows (or columns) of pixels extracted separately from consecutive video frames
at co-located positions (indicated by the red lines).

Figure 10: Qualitative comparison on Vid4 for $\times 4$ upscaling. Zoom in
for better visualization.  Figure 11: Qualitative comparison on Vimeo-90K-T
for $\times 4$ upscaling. Zoom in for better visualization.

Figure 12: Qualitative frame-by-frame comparison between MIMO-VRN and MIMO-
VRN-C, with a GoF size of 5. The images shown are $\times 4$ upscaled HR video
frames of Vid4. Figure 13: Sample LR video frames from Vid4. Our models show
comparable visual quality to the bicubic method.