11institutetext: Research Institute of Health Science (IUNICS) and Department
of Mathematics and Computer Science, University of the Balearic Islands,
E-07122 Palma de Mallorca, Spain 11email<EMAIL_ADDRESS>
# Two results on expected values of imbalance indices of phylogenetic trees

Arnau Mir  Francesc Rosselló

###### Abstract

We compute an explicit formula for the expected value of the Colless index of
a phylogenetic tree generated under the Yule model, and an explicit formula
for the expected value of the Sackin index of a phylogenetic tree generated
under the uniform model.

##  1 Introduction

A _phylogenetic tree_ is a representation of the shared evolutionary history
of a set of extant species. From the mathematical point a view, it is a leaf-
labeled rooted tree, with its leaves representing the extant species under
study, its internal nodes representing common ancestors of some of them, the
root representing the most recent common ancestor of all of them, and the arcs
representing direct descendance through mutations. In this paper we only
consider _binary_ phylogenetic trees, where every internal node has exactly
two children.

There are several stochastic models of the evolutionary processes that produce
phylogenetic trees. Two of the most popular are the Yule and the uniform
models. In the _Yule_ , or _Equal-Rate Markov_ , model [8, 23], starting with
a node, at every step a leaf is chosen randomly and uniformly, and it is
replaced by a _cherry_ (a phylogenetic tree consisting only of a root and two
leaves). Finally, the labels are assigned randomly and uniformly to the leaves
once the desired number of leaves is reached. Under this model of evolution,
different trees with the same number of leaves may have different
probabilities. More specifically, if $T$ is a binary phylogenetic tree with
$n$ leaves, and for every internal node $z$ we denote by $\kappa_{T}(z)$ the
number of its descendant leaves, then the probability of $T$ under the Yule
model is [4, 21]

$P_{Y}(T)=\frac{2^{n-1}}{n!}\prod_{v\
\mathrm{internal}}\frac{1}{\kappa_{T}(v)-1}.$

On the other hand, the main feature of the _uniform_ , or _Proportional to
Distinguishable Arrangements_ , model [17] is that all phylogenetic trees with
the same number of leaves have the same probability. From the point of view of
tree growth, this corresponds to a process where, starting with a node labeled
1, at the $k$-th step a new pendant arc, ending in the leaf labeled $k+1$, is
added either to a new root or to some edge (with all possible locations of
this new pendant arc equiprobable). Notice that this is not an explicit model
of evolution, only of tree growth.

The study of the probabilistic distributions of indices associated to
phylogenetic trees under different stochastic models of phylogenetic tree
growth has received a lot of interest in the last decades [12, 19]. The
ultimate goal of this line of research is to be able to take as null model
some stochastic model of phylogenetic tree growth and evaluate against it the
indices of a sample of phylogenetic trees reconstructed from data. Two of the
most popular indices used in this connection, measuring the degree of
symmetry, or _balance_ , of a tree, are Sackin’s [18] and Colless’ [6]
indices, which we define later in the main body of this paper, but there are
many other measures associated to phylogenetic trees that have been used in
this context, like for instance other imbalance indices [7, Chap. 33] or the
number of cherries of trees [20].

Several properties of the distributions of Sackin’s $S$ and Colless’ $C$
indices have been studied in the literature under different models [3, 9, 13,
14, 15, 16, 21]. In particular, their expected values have been studied under
the Yule and the uniform model. The results published so far on these expected
values have been the following. Let $S_{n}$ and $C_{n}$ be the random
variables defined by choosing a binary phylogenetic tree $T$ with $n$ leaves
and computing $S(T)$ or $C(T)$, respectively. Then:

  * •

Under the Yule model,

    * –

$E_{Y}(S_{n})=2n\sum\limits_{j=2}^{n}1/j$ [9].

    * –

$E_{Y}(C_{n})=n\log(n)+(\gamma-1-\log(2))n+o(n)$ [3], where $\gamma$ is the
Euler constant.

  * •

Under the uniform model,

    * –

$E_{U}(S_{n})\sim\sqrt{\pi}n^{3/2}$ [22].

    * –

$E_{U}(C_{n})\sim\sqrt{\pi}n^{3/2}$ [3].

And, for instance, these are the formulas used by the R package apTreeshape
[1] to compute the expected value of these indices for a given number of
leaves. Let us also mention that Rogers [15] found a recursive formula for the
moment-generating functions of $C$ and $S$, which allowed him to compute
$E_{Y}(C_{n})$ and $E_{U}(C_{n})$ for $n=1,\ldots,50$, but he did not obtain
any explicit formula for them.

In this paper we obtain explicit formulas for $E_{Y}(C_{n})$ and
$E_{U}(S_{n})$. Namely,

$E_{Y}(C_{n})=n\sum_{j=2}^{\lfloor n/2\rfloor}\frac{1}{j}+\delta_{odd}(n),$

where $\delta_{odd}(n)=1$ if $n$ is odd, and $\delta_{odd}(n)=0$ if $n$ is
even, and

$E_{U}(S_{n})=\frac{n}{2n-3}{}_{3}F_{2}\bigg{(}\begin{array}[]{l}2,\ 2,\
2-n\\\\[-2.15277pt] 1,\ 4-2n\end{array};2\bigg{)},$

where ${}_{3}F_{2}$ is a _hypergeometric function_ [2] that can be directly
computed with many software systems, like Mathematica or R. These formulas
thus contribute to our knowledge of the probability distributions of these
indices, and yield precise values which can be used is tests.

##  2 Preliminaries and notations

In this paper, by a _phylogenetic tree_ on a set $S$ of taxa we mean a binary
rooted tree with its leaves bijectively labeled in the set $S$. To simplify
the language, we shall always identify a leaf of a phylogenetic tree with its
label. We shall also use the term _phylogenetic tree with $n$ leaves_ to refer
to a phylogenetic tree on the set $\\{1,\ldots,n\\}$. We shall denote by
$L(T)$ the set of leaves of a phylogenetic tree $T$ and by $V_{int}(T)$ its
set of internal nodes.

Let $\mathcal{T}(S)$ be the set of isomorphism classes of phylogenetic trees
on a set $S$ of taxa, and set $\mathcal{T}_{n}=\mathcal{T}(\\{1,\ldots,n\\})$.
It is well known [7, Ch.3] that $|\mathcal{T}_{1}|=1$ and, for every
$n\geqslant 2$,

$|\mathcal{T}_{n}|=(2n-3)!!=(2n-3)(2n-5)\cdots 3\cdot 1.$

Whenever there exists a path from $u$ to $v$ in a phylogenetic tree $T$, we
shall say that $v$ is a _descendant_ of $u$. The _cluster_ of a node $v$ in
$T$ is the set $C_{T}(v)$ of its descendant leaves, an we shall denote by
$\kappa_{T}(v)$ the cardinal $|C_{T}(v)|$, that is, the number of descendant
leaves of $v$. The _depth_ $\delta_{T}(v)$ of a node $v$ in a phylogenetic
tree $T$ is the length (number of arcs) of the unique path from the root $r$
to $v$.

Given two phylogenetic trees $T_{1},T_{2}$ on disjoint sets of taxa
$S_{1},S_{2}$, respectively, we shall denote by $T_{1}\widehat{\ }\,T_{2}$ the
tree on $S_{1}\cup S_{2}$ obtained by connecting the roots of $T_{1}$ and
$T_{2}$ to a (new) common parent $r$. Every tree in $\mathcal{T}_{n}$ is
obtained as $T_{k}\widehat{\ }\,{}T_{n-k}$, for some subset
$S_{k}\subseteq\\{1,\ldots,n\\}$ with $k$ elements (with $1\leqslant
k\leqslant n-1$), some tree $T_{k}$ on $S_{k}$ and some tree $T_{n-k}$ on
$S_{k}^{c}=\\{1,\ldots,n\\}\setminus S_{k}$: actually, if we perform in this
order the choices necessary to produce a tree $T\in\mathcal{T}_{n}$ in this
way, we obtain every tree in $\mathcal{T}_{n}$ twice.

An _ordered $m$-forest_ on a set $S$ is an ordered sequence of $m$
phylogenetic trees $(T_{1},T_{2},\ldots,T_{m})$, each $T_{i}$ on a set $S_{i}$
of taxa, such that these sets $S_{i}$ are pairwise disjoint and their union is
$S$. Let $\mathcal{F}_{m,n}$ be the set of isomorphism classes of ordered
$m$-forests on $\\{1,\ldots,n\\}$. It is known (see, for instance, [11, Lem.
1]) that for every $n\geqslant m\geqslant 1$,

$|\mathcal{F}_{m,n}|=\frac{(2n-m-1)!m}{(n-m)!2^{n-m}}.$

##  3 Expected value of the Colless index under the Yule model

Let $T$ be a phylogenetic tree. For every $v\in V_{int}(T)$, the _balance
value_ of $v$ is $bal_{T}(v)=|\kappa_{T}(v_{1})-\kappa_{T}(v_{2})|$, where
$v_{1}$ and $v_{2}$ are its children. The _Colless index_ [6] of a
phylogenetic tree $T\in\mathcal{T}_{n}$ is

$C(T)=\sum_{v\in V_{int}(T)}bal_{T}(v).$

###### Lemma 1

If $T_{k}\in\mathcal{T}_{k}$ and $T_{n-k}\in\mathcal{T}_{n-k}$, then

  1. (a)

$C(T_{k}\widehat{\ }\,{}T_{n-k})=C(T_{k})+C(T_{n-k})+|2n-k|$

  2. (b)

$P_{Y}(T_{k}\widehat{\
}\,{}T_{n-k})=\dfrac{2}{(n-1)\binom{n}{k}}P_{Y}(T_{k})P_{Y}(T_{n-k})$

where $P_{Y}$ denotes the probability of a phylogenetic tree under the Yule
model.

###### Proof

Assertion (a) is well known, and a direct consequence of the definition of
$C$. Assertion (b) is a direct consequence of the explicit probabilities of
$T_{k}$, $T_{n-k}$ and $T_{k}\widehat{\ }\,{}T_{n-k}$ under the Yule model,
and the fact that $V_{int}(T_{k}\widehat{\ }\,{}T_{n-k})=V_{int}(T_{k})\cup
V_{int}(T_{n-k})\cup\\{r\\}$, these unions being disjoint.

###### Lemma 2

Let $I:\bigcup_{n\in\mathbb{N}}\mathcal{T}_{n}\to\mathbb{R}$ be a mapping such
that, for every phylogenetic trees $T_{1},T_{2}$ on disjoint sets of taxa
$S_{1},S_{2}$, respectively,

$I(T_{1}\widehat{\ }\,T_{2})=I(T_{1})+I(T_{2})+f(|S_{1}|,|S_{2}|)$

for some mapping $f:\mathbb{N}\times\mathbb{N}\to\mathbb{R}$. For every
$n\geqslant 1$, let $I_{n}$ be the random variable that chooses a tree
$T_{n}\in\mathcal{T}_{n}$ and computes $I(T_{n})$, and let $E_{Y}(I_{n})$ be
its expected value under the Yule model. Then,

$E_{Y}(I_{n})=\frac{1}{n-1}\Big{(}2\sum_{k=1}^{n-1}E_{Y}(I_{k})+\sum_{k=1}^{n-1}f(k,n-k)\Big{)}$

###### Proof

We compute $E_{Y}(I_{n})$ using its very definition and Lemma 1.(b):

$\begin{array}[]{l}E_{Y}(I_{n})\displaystyle=\sum_{T_{n}\in\mathcal{T}_{n}}I(T_{n})\cdot
p_{Y}(T_{n})\\\
\quad\displaystyle=\sum_{k=1}^{n-1}\sum_{S_{k}\subset\\{1,\ldots,n\\}\atop|S_{k}|=k}\sum_{T_{k}\in\mathcal{T}(S_{k})}\sum_{T_{n-k}\in\mathcal{T}(S_{k})}I(T_{k}\widehat{\
}\,{}T_{n-k})\cdot p_{Y}(T_{k}\widehat{\ }\,{}T_{n-k})\\\
\quad\displaystyle=\frac{1}{2}\sum_{k=1}^{n-1}\binom{n}{k}\sum_{T_{k}\in\mathcal{T}_{k}}\sum_{T_{n-k}\in\mathcal{T}_{n-k}}(I(T_{k})+I(T_{n-k})\\\
\quad\displaystyle\qquad\qquad\qquad\qquad\qquad+f(k,n-k))\cdot\frac{2}{(n-1)\binom{n}{k}}P_{Y}(T_{k})P_{Y}(T_{n-k})\\\
\quad\displaystyle=\frac{1}{n-1}\sum_{k=1}^{n-1}\sum_{T_{k}}\sum_{T_{n-k}}(I(T_{k})+I(T_{n-k})+f(k,n-k))P_{Y}(T_{k})P_{Y}(T_{n-k})\\\
\quad\displaystyle=\frac{1}{n-1}\sum_{k=1}^{n-1}\Big{(}\sum_{T_{k}}\sum_{T_{n-k}}I(T_{k})P_{Y}(T_{k})P_{Y}(T_{n-k})\\\
\quad\displaystyle\qquad\qquad\qquad\qquad+\sum_{T_{k}}\sum_{T_{n-k}}I(T_{n-k})P_{Y}(T_{k})P_{Y}(T_{n-k})\\\
\quad\displaystyle\qquad\qquad\qquad\qquad+\sum_{T_{k}}\sum_{T_{n-k}}f(k,n-k)P_{Y}(T_{k})P_{Y}(T_{n-k})\Big{)}\\\
\quad\displaystyle=\frac{1}{n-1}\sum_{k=1}^{n-1}\Big{(}\sum_{T_{k}}I(T_{k})P_{Y}(T_{k})+\sum_{T_{n-k}}I(T_{n-k})P_{Y}(T_{n-k})+f(k,n-k)\Big{)}\\\
\end{array}$
$\begin{array}[]{l}\quad\displaystyle=\frac{1}{n-1}\sum_{k=1}^{n-1}(E_{Y}(I_{k})+E_{Y}(I_{n-k})+f(k,n-k))\\\
\quad\displaystyle=\frac{1}{n-1}\Big{(}2\sum_{k=1}^{n-1}E_{Y}(I_{k})+\sum_{k=1}^{n-1}f(k,n-k)\Big{)}\end{array}$

as we claimed.

Mappings $I$ satisfying the hypothesis in the previous lemma are a special
case of _binary recursive tree shape statistics_ in the sense of [10].

###### Theorem 3.1

Let $C_{n}$ be the random variable that chooses a tree $T\in\mathcal{T}_{n}$
and computes its Colless index $C(T_{n})$. Its expected value under the Yule
model is

$E_{Y}(C_{n})=n\sum_{j=2}^{\lfloor n/2\rfloor}\frac{1}{j}+\delta_{odd}(n),$

where $\delta_{odd}(n)=1$ if $n$ is odd, and $\delta_{odd}(n)=0$ if $n$ is
even.

###### Proof

To simplify the notations, we shall denote $E_{Y}(C_{n})$ simply by $E_{n}$.
By Lemmas 1.(a) and 2,

$E_{n}=\frac{1}{n-1}\Big{(}2\sum_{k=1}^{n-1}E_{k}+\sum_{k=1}^{n-1}|n-2k|\Big{)}.$

Now a simple computation shows that

$\sum_{k=1}^{n-1}|n-2k|=\left\\{\begin{array}[]{ll}\dfrac{n(n-2)}{2}&\mbox{ if
$n$ is even}\\\ \dfrac{(n-1)^{2}}{2}&\mbox{ if $n$ is odd}\end{array}\right.$

and therefore

$E_{n}=\frac{2}{n-1}\sum_{k=1}^{n-1}E_{k}+\left\\{\begin{array}[]{ll}\dfrac{n(n-2)}{2(n-1)}&\mbox{
if $n$ is even}\\\ \dfrac{n-1}{2}&\mbox{ if $n$ is odd}\end{array}\right.$

In order to obtain a recurrence of order one from this expression, we
distinguish the case when $n$ is even from the case when $n$ is odd.

  * •

When $n$ is even

$E_{n}=\frac{2}{n-1}\sum_{k=1}^{n-1}E_{k}+\frac{n(n-2)}{2(n-1)},\quad
E_{n-1}=\frac{2}{n-2}\sum_{k=1}^{n-2}E_{k}+\dfrac{n-2}{2}$

and then

$\begin{array}[]{rl}E_{n}&\displaystyle=\frac{2}{n-1}E_{n-1}+\frac{2}{n-1}\sum_{k=1}^{n-2}E_{k}+\frac{n(n-2)}{2(n-1)}\\\
&\displaystyle=\frac{2}{n-1}E_{n-1}+\frac{n-2}{n-1}\cdot\frac{2}{n-2}\sum_{k=1}^{n-2}E_{k}+\frac{n-2}{n-1}\cdot\dfrac{n-2}{2}+\frac{n-2}{n-1}\\\
&\displaystyle=\frac{2}{n-1}E_{n-1}+\frac{n-2}{n-1}E_{n-1}+\frac{n-2}{n-1}\\\
&\displaystyle=\frac{n}{n-1}E_{n-1}+\frac{n-2}{n-1}\end{array}$

  * •

When $n$ is odd

$E_{n}=\frac{2}{n-1}\sum_{k=1}^{n-1}E_{k}+\frac{n-1}{2},\quad
E_{n-1}=\frac{2}{n-2}\sum_{k=1}^{n-2}E_{k}+\dfrac{(n-1)(n-3)}{2(n-2)}$

and then

$\begin{array}[]{rl}E_{n}&\displaystyle=\frac{2}{n-1}E_{n-1}+\frac{2}{n-1}\sum_{k=1}^{n-2}E_{k}+\frac{n-1}{2}\\\
&\displaystyle=\frac{2}{n-1}E_{n-1}+\frac{n-2}{n-1}\cdot\frac{2}{n-2}\sum_{k=1}^{n-2}E_{k}+\frac{n-2}{n-1}\cdot\dfrac{(n-1)(n-3)}{2(n-2)}+1\\\
&\displaystyle=\frac{2}{n-1}E_{n-1}+\frac{n-2}{n-1}E_{n-1}+1\\\
&\displaystyle=\frac{n}{n-1}E_{n-1}+1\end{array}$

So, in summary,

$E_{n}=\frac{n}{n-1}E_{n-1}+\left\\{\begin{array}[]{ll}\dfrac{n-2}{n-1}&\mbox{
if $n$ is even}\\\ 1&\mbox{ if $n$ is odd}\end{array}\right.$

In particular, if $n$ is even,

$\begin{array}[]{rl}E_{n}&\displaystyle=\frac{n}{n-1}E_{n-1}+\dfrac{n-2}{n-1}=\frac{n}{n-1}\Big{(}\frac{n-1}{n-2}E_{n-2}+1\Big{)}+\dfrac{n-2}{n-1}\\\
&\displaystyle=\frac{n}{n-2}E_{n-2}+2\end{array}$

Setting $x_{n}=E_{n}/n$, this equation becomes

$x_{n}=x_{n-2}+\frac{2}{n}$

whose solution (for even numbered terms) with $x_{2}=E_{2}/2=0$ is

$x_{n}=\sum_{i=2}^{n/2}\frac{1}{i}.$

Therefore, when $n$ is even,

$E_{n}=n\sum_{i=2}^{n/2}\frac{1}{i},$

and when $n$ is odd,

$E_{n}=\frac{n}{n-1}E_{n-1}+1=\frac{n}{n-1}\cdot(n-1)\sum_{i=2}^{(n-1)/2}\frac{1}{i}+1=1+n\sum_{i=2}^{\lfloor
n/2\rfloor}\frac{1}{i}$

as we claimed.

##  4 Expected value of the Sackin index under the uniform model

The _Sackin index_ [18] of a phylogenetic tree $T\in\mathcal{T}_{n}$ is
defined as the sum of the depths of its leaves:

$S(T)=\sum_{i=1}^{n}\delta_{T}(i).$

Alternatively,

$S(T)=\sum_{v\in V_{int}(T)}\kappa_{T}(v).$

Let $S_{n}$ be the random variable that chooses a tree $T\in\mathcal{T}_{n}$
and computes its Sackin index $S(T)$. Since, under the uniform model, all
trees in $\mathcal{T}_{n}$ have probability $1/((2n-3)!!)$, the expected value
of $S_{n}$ under the uniform model is

$\frac{\sum_{T\in\mathcal{T}_{n}}S(T)}{(2n-3)!!}.$

So, we need to compute the numerator in this fraction. Now, for every
$k=1,\ldots,n-1$, let

$c_{k,n}=|\\{T\in\mathcal{T}_{n}\mid\delta_{T}(1)=k\\}|.$

###### Lemma 3

For every $n\geqslant 3$,
$\displaystyle\sum_{T\in\mathcal{T}_{n}}S(T)=n\sum_{k=1}^{n-1}k\cdot c_{k,n}$

###### Proof

Notice that, for every $1\leqslant i\leqslant n$,

$|\\{T\in\mathcal{T}_{n}\mid\delta_{T}(i)=k\\}|=|\\{T\in\mathcal{T}_{n}\mid\delta_{T}(1)=k\\}|.$

Then

$\begin{array}[]{rl}\displaystyle\sum_{T\in\mathcal{T}_{n}}S(T)&\displaystyle=\sum_{T\in\mathcal{T}_{n}}\sum_{i=1}^{n}\delta_{T}(i)=\sum_{i=1}^{n}\sum_{T\in\mathcal{T}_{n}}\delta_{T}(i)\\\
&\displaystyle=\sum_{i=1}^{n}\sum_{k=1}^{n-1}k\cdot|\\{T\in\mathcal{T}_{n}\mid\delta_{T}(i)=k\\}|\\\
&\displaystyle=\sum_{i=1}^{n}\sum_{k=1}^{n-1}k\cdot|\\{T\in\mathcal{T}_{n}\mid\delta_{T}(1)=k\\}|=n\sum_{k=1}^{n-1}k\cdot
c_{k,n}\end{array}$

###### Lemma 4

For every $n\geqslant 2$ and $k=1,\ldots,n-1$,

$c_{k,n}=\frac{(2n-k-3)!k}{(n-k-1)!2^{n-k-1}}.$

###### Proof

To compute $c_{k,n}$ for $k\geqslant 1$, notice that every tree
$T\in\mathcal{T}_{n}$ such that $\delta(1)=k$ will have the form described in
Fig. 1. Therefore, it is determined by the ordered $k$-forest
$T_{1},T_{2},\ldots,T_{k}$ on $\\{2,\ldots,n\\}$, and thus

$c_{k,n}=|\mathcal{F}_{k,n-1}|=\frac{(2n-k-3)!k}{(n-k-1)!2^{n-k-1}}.$

$1$...$T_{k}$$T_{2}$$T_{1}$ Figure 1:  The structure of a tree $T$ with
$\delta_{T}(1)=k$.

Now, recall that the (_generalized_) _hypergeometric function_ ${}_{p}F_{q}$
is defined [2] as

${}_{p}F_{q}\bigg{(}\begin{array}[]{rrr}a_{1},&\ldots,&a_{p}\\\\[-2.15277pt]
b_{1},&\ldots,&b_{q}\end{array};z\bigg{)}=\sum_{k\geqslant
0}\frac{(a_{1})_{k}\cdots(a_{p})_{k}}{(b_{1})_{k}\cdots(b_{q})_{k}}\cdot\frac{z^{k}}{k!},$

where $(a)_{k}:=a\cdot(a+1)\cdots(a+k-1)$. Many popular software systems, like
Mathematica or R, have implementations of these functions.

###### Theorem 4.1

The expected value of the random variable $S_{n}$ under the uniform model is

$E_{U}(S_{n})=\frac{n}{2n-3}{}_{3}F_{2}\bigg{(}\begin{array}[]{l}2,\ 2,\
2-n\\\\[-2.15277pt] 1,\ 4-2n\end{array};2\bigg{)}$

###### Proof

As we have already mentioned,

$E_{U}(S_{n})=\frac{\sum_{T\in\mathcal{T}_{n}}S(T)}{(2n-3)!!}=\frac{n}{(2n-3)!!}\sum_{k=1}^{n-1}k\cdot
c_{k,n}=\frac{n}{(2n-3)!!}\sum_{k=1}^{n-1}\frac{(2n-k-3)!k^{2}}{(n-k-1)!2^{n-k-1}}$

Now

$\begin{array}[]{rl}\displaystyle\frac{nk^{2}(2n-k-3)!}{(2n-3)!!(n-k-1)!2^{n-k-1}}&\displaystyle=\frac{nk^{2}(2n-k-3)!2^{n-2}(n-2)!}{(2n-3)!(n-k-1)!2^{n-k-1}}\\\\[8.61108pt]
&\displaystyle=\frac{nk^{2}(2n-k-3)!2^{n-2}(n-2)!k!}{(2n-3)!(n-k-1)!2^{n-k-1}k!}\\\\[8.61108pt]
&\displaystyle=\frac{nk^{2}2^{k-1}\binom{n-1}{k}}{(n-1)\binom{2n-3}{k}}\end{array}$

and thus

$\begin{array}[]{rl}E_{U}(S_{n})&=\displaystyle\frac{n}{n-1}\sum_{k=1}^{n-1}k^{2}2^{k-1}\cdot\frac{\binom{n-1}{k}}{\binom{2n-3}{k}}\\\
&=\displaystyle\frac{n}{n-1}\sum_{k=1}^{n-1}\frac{k^{2}2^{k-1}(n-1)(n-2)(n-3)\cdots(n-k)}{(2n-3)(2n-4)(2n-5)\cdots(2n-k-2)}\\\
&=\displaystyle\frac{n}{2n-3}\sum_{k=1}^{n-1}\frac{k^{2}2^{k-1}(n-2)(n-3)\cdots(n-k)}{(2n-4)(2n-5)\cdots(2n-k-2)}\\\
&=\displaystyle\frac{n}{2n-3}\sum_{k=1}^{n-1}\frac{k^{2}2^{k-1}(2-n)(2-n+1)\cdots(-n+k)}{(4-2n)(4-2n+1)\cdots(2-2n+k)}\\\
&=\displaystyle\frac{n}{2n-3}\sum_{k=0}^{n-2}\frac{(k+1)^{2}2^{k}(2-n)(2-n+1)\cdots(1-n+k)}{(4-2n)(4-2n+1)\cdots(3-2n+k)}\\\
&=\displaystyle\frac{n}{2n-3}\sum_{k\geqslant
0}\frac{((k+1)!)^{2}(2-n)(2-n+1)\cdots(1-n+k)\cdot
2^{k}}{(k!)^{2}(4-2n)(4-2n+1)\cdots(3-2n+k)}\\\
&=\displaystyle\frac{n}{2n-3}\sum_{k\geqslant
0}\frac{(2)_{k}(2)_{k}(2-n)_{k}}{(1)_{k}((4-2n)_{k}}\cdot\frac{2^{k}}{k!}=\dfrac{n}{2n-3}{}_{3}F_{2}\bigg{(}\begin{array}[]{l}2,\
2,\ 2-n\\\\[-2.15277pt] 1,\ 4-2n\end{array};2\bigg{)}\end{array}$

as we claimed.

##  5 Conclusion

In this paper we have obtained explicit formulas for the expected value of the
Sackin index under the uniform model and the Colless index under the Yule
model. These results add up to the already known expected value of the Sackin
index under the Yule model [9]. For any $n$, these expected values are easily
computed directly using for instance the software system R, and can be used
instead of their estimations in packages like apTreeshape [1] or SymmeTREE
[5].

It remains open the problem of finding an explicit formula for the expected
value of the Colless index under the uniform model.

Acknowledgements. The research reported in this paper has been partially
supported by the Spanish government and the UE FEDER program, through projects
MTM2009-07165 and TIN2008-04487-E/TIN. We thank G. Cardona and M. Llabrés for
several comments on this work.

## References

  * [1] N. Bortolussi, E. Durand, M. Blum, O. François, apTreeshape: statistical analysis of phylogenetic tree shape. Bioinformatics 22 (2006), 363–364.
  * [2] W.N. Bayley, Generalized Hypergeometric Series. Cambridge Tracts in Mathematics and Mathematical Physics 32, Stechert-Hafner Service Inc. (1964).
  * [3] M. G. B. Blum, O. François, S. Janson, The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance. Ann. Appl. Probab. 16 (2006), 2195–2214.
  * [4] J. Brown, Probabilities of evolutionary trees. Syst. Biol. 43 (1994), 78–91.
  * [5] K. M. Chan, B. R. Moore, SymmeTREE: Whole-tree analysis of differential diversification rates. Bioinformatics 21 (2005), 1709–1710.
  * [6] D. H. Colless, Review of “Phylogenetics: the theory and practice of phylogenetic systematics”. Sys. Zool. 31 (1982), 100–104.
  * [7] J. Felsenstein, Inferring Phylogenies. Sinauer Associates Inc., 2004.
  * [8] E. Harding, The probabilities of rooted tree-shapes generated by random bifurcation. Adv. Appl. Prob. 3 (1971), 44–77.
  * [9] M. Kirkpatrick, M. Slatkin, Searching for evolutionary patterns in the shape of a phylogenetic tree. Evolution 47 (1993), 1171–1181.
  * [10] F. Matsen, Optimization Over a Class of Tree Shape Statistics. IEEE/ACM Trans. Comput. Biol. Bioinf. 4 (2007), 506–512.
  * [11] A. Mir, F. Rosselló, The mean value of the squared path-difference distance for rooted phylogenetic trees. J. Math. Anal. Appl. 371 (2010), 168–176.
  * [12] A. Mooers, S. B. Heard, Inferring evolutionary process from phylogenetic tree shape. Quart. Rev. Biol. 72 (1997) 31–54.
  * [13] W. H. Mulder, Probability distributions of ancestries and genealogical distances on stochastically generated rooted binary trees. J. Theor. Biol. 280 (2011), 139–145.
  * [14] J. S. Rogers, Response of tree imbalance to number of terminal taxa. Sys. Biol. 42 (1993), 102–105.
  * [15] J. S. Rogers, Central moments and probability distributions of Colless’s coefficient of tree imbalance. Evolution 48 (1994), 2026–2036.
  * [16] J. S. Rogers, Central moments and probability distributions of three measures of phylogenetic tree imbalance, Sys. Biol. 45 (1996), 99–110.
  * [17] D. E. Rosen, Vicariant Patterns and Historical Explanation in Biogeography. Syst. Biol. 27 (1978), 159–188.
  * [18] M. J. Sackin, “Good” and “bad” phenograms. Sys. Zool. 21 (1972), 225–226.
  * [19] K.T. Shao, R. Sokal, Tree balance. Sys. Zool. 39 (1990), 226–276.
  * [20] M. Steel, A. McKenzie, Distributions of cherries for two models of trees. Math. Biosc. 164 (2000), 81–92.
  * [21] M. Steel, A. McKenzie, Properties of phylogenetic trees generated by Yule-type speciation models. Math. Biosc. 170 (2001), 91–112.
  * [22] L. Takács, A Bernoulli Excursion and Its Various Applications. Adv. Appl. Prob. 23 (1991), 557–585.
  * [23] G. U. Yule, A mathematical theory of evolution based on the conclusions of Dr J. C. Willis. Phil. Trans. Royal Soc. (London) Series B 213 (1924), 21–87.


# FaPN: Feature-aligned Pyramid Network for Dense Image Prediction

Shihua Huang Zhichao Lu Ran Cheng Cheng He
Southern University of Science and Technology
{shihuahuang95, luzhichaocn, ranchengcn<EMAIL_ADDRESS>Corresponding
author.Authors are with Department of Computer Science and Engineering.

###### Abstract

Recent advancements in deep neural networks have made remarkable leap-forwards
in dense image prediction. However, the issue of feature alignment remains as
neglected by most existing approaches for simplicity. Direct pixel addition
between upsampled and local features leads to feature maps with misaligned
contexts that, in turn, translate to mis-classifications in prediction,
especially on object boundaries. In this paper, we propose a feature alignment
module that learns transformation offsets of pixels to contextually align
upsampled higher-level features; and another feature selection module to
emphasize the lower-level features with rich spatial details. We then
integrate these two modules in a top-down pyramidal architecture and present
the Feature-aligned Pyramid Network (FaPN). Extensive experimental evaluations
on four dense prediction tasks and four datasets have demonstrated the
efficacy of FaPN, yielding an overall improvement of 1.2 - 2.6 points in AP /
mIoU over FPN when paired with Faster / Mask R-CNN. In particular, our FaPN
achieves the state-of-the-art of 56.7% mIoU on ADE20K when integrated within
MaskFormer. The code is available from https://github.com/EMI-Group/FaPN.

##  1 Introduction

Dense prediction is a collection of computer vision tasks that aim at labeling
every pixel in an image with a pre-defined class. It plays a fundamental role
in scene understanding and is of great importance to real-world applications,
such as autonomous driving [7], medical imaging [45], augmented reality [1],
_etc_. The modern solutions for these tasks are built upon Convolutional
Neural Networks (CNNs). With the recent advancements in CNN architectures, a
steady stream of promising empirical leap-forwards was reported across a wide
range of dense prediction tasks, including object detection [41, 27, 40],
semantic segmentation [29, 4], instance segmentation [13, 26], and panoptic
segmentation [20, 19], to name a few.

Figure 1: Comparisons between FPN and FaPN: (_Top row_) Qualitatively, FaPN
significantly improves the performance on object boundaries as opposed to its
counterpart, _i.e_. FPN [24]. (_Bottom row_) Quantitatively, FaPN’s
improvements over FPN are consistent across different tasks, backbones, and
object scales. Best view in color.  Figure 2: Example pairs of results from
FPN [24] and our FaPN. Both methods are implemented in Mask R-CNN [13] with
ResNet50 [14] being the backbone and PointRend [21] as the mask head.
Qualitatively, FaPN significantly improves the performance on object
boundaries. Images are randomly chosen from [25] and [9] for instance (_left_)
and semantic (_right_) segmentation, respectively. More visualization examples
are available in the supplementary materials.

Dense prediction requires both rich spatial details for object location and
strong semantics for object classification, which most likely reside at
different resolution / scale levels [29]. How to effectively generate a
hierarchy of features at different scales becomes one of the key barriers to
overcome in handling dense prediction tasks [24]. Broadly speaking, there are
two common practices to address this issue. The first kind uses atrous
convolutions with different atrous rates to effectively capture long-range
information (_i.e_. semantic context) without reducing spatial resolution [4].
The other kind builds a top-down feature pyramid based on the default bottom-
top pathway of a ConvNet [2]. More specifically, the (higher-level) spatially
coarser feature maps are upsampled before merging with the corresponding
feature maps from the bottom-up path-way. However, there are inaccurate
correspondences (_i.e_. _feature misalignment_) between the bottom-up and
upsampled features owing to the non-learnable nature of the commonly-used
upsampling operations (_e.g_. nearest neighbor) and the repeated applications
of downsampling and upsampling. The misaligned features, in turn, adversely
affects the learning in the subsequent layers, resulting in mis-
classifications in the final predictions, especially around the object
boundaries. To address the aforementioned issue, we propose a feature
alignment module that learns to align the upsampled feature maps to a set of
reference feature maps by adjusting each sampling location in a convolutional
kernel with a learned offset. We further propose a feature selection module to
adaptively emphasize the bottom-up feature maps containing excessive spatial
details for accurate locating. We then integrate these two modules in a top-
down pyramidal architecture and propose the _Feature-aligned Pyramid Network
(FaPN)_.

Conceptually, FaPN can be easily incorporated to existing bottom-up ConvNet
backbones [14, 30, 34, 32] to generate a pyramid of features at multiple
scales [24]. We implement FaPN in modern dense prediction frameworks (Faster
R-CNN [41], Mask R-CNN [13], PointRend [21], MaskFormer [8], PanopticFPN [19],
and PanopticFCN [23]), and demonstrate its efficacy on object detection,
semantic, instance and panoptic segmentation. Extensive evaluations on
multiple challenging datasets suggest that FaPN leads to a significant
improvement in dense prediction performance, especially for small objects and
on object boundaries. Moreover, FaPN can also be easily extended to real-time
semantic segmentation by pairing it with a lightweight bottom-up backbone [14,
33, 31]. Without bells and whistles, FaPN achieves favorable performance
against existing dedicated real-time methods. Our key contributions are:

– We first develop (i) a feature alignment module that learns transformation
offsets of pixels to contextually align upsampled (higher-level) features; and
(ii) another feature selection module to emphasize (lower-level) features with
rich spatial details.

– With the integration of these two contributions, we present, _Feature-
aligned Pyramid Network (FaPN)_ , an enhanced drop-in replacement of FPN [24],
for generating multi-scale features.

– We present a thorough experimental evaluation demonstrating the efficacy and
value of each component of FaPN across _four_ dense prediction tasks,
including object detection, semantic, instance, and panoptic segmentation on
three benchmark datasets, including MS COCO [25], Cityscapes [9], COCO-
Stuff-10K [3].

– Empirically, we demonstrate that our FaPN leads to a significant improvement
of 1.2% - 2.6% in performance (AP / mIoU) over the original FPN [24].
Furthermore, our FaPN achieves the state-of-the-art of 56.7% mIoU on ADE20K
when integrated within MaskFormer [8].

##  2 Related Work

Feature Pyramid Network Backbone: The existing dense image prediction methods
can be broadly divided into two groups. The first group utilizes atrous
convolutions to enlarge the receptive field of convolutional filters for
capturing long-range information without reducing resolutions spatially.
DeepLab [4] is one of the earliest method that adopt atrous convolution for
semantic segmentation. It introduced an Atrous Spatial Pyramid Pooling module
(ASPP) comprised of atrous convolutions with different atrous rates to
aggregate multi-scale context from high-resolution feature maps. Building upon
ASPP, a family of methods [4, 5, 6] were developed. However, the lack of the
ability to generate feature maps at multiple scales restricts the application
of this type of methods to other dense prediction tasks beyond semantic
segmentation. The second group of methods focuses on building an encoder-
decoder network, _i.e_. bottom-up and top-down pathways. The top-down pathway
is used to back-propagate the high-level semantic context into the low-level
features via a step-by-step upsampling. There is a plethora of encoder-decoder
methods [38, 12, 24, 13, 19, 44, 46] proposed for different dense image
prediction tasks. DeconvNet [38] is one of the earliest works that proposed to
use upsample operations with learnable parameters, _i.e_. deconvolution. DSSD
[12] and FPN [24] are the extensions of SSD [27] and Faster R-CNN [41]
respectively for object detection. Mask R-CNN [13] and SOLOs [44, 46] are used
for real-time instance segmentation. Moreover, Kirillov _et al_. propose the
Panoptic FPN [19] for panoptic segmentation.

Feature Alignment: In case of the increasing loss of boundary detail with the
step-by-step downsampling, SegNet[2] stores the max-pooling indices in its
encoder and upsamples feature maps in the decoder with the corresponding
stored max-pooling indices. Instead of memorizing the spatial information in
the encoder previously as SegNet, GUN [35] tries to learn the guidance offsets
before upsampling in the decoder and then upsamples feature maps following
those offsets. To solve the misalignment between extracted features and the
RoI caused by the quantizations in RoIPool, RoIAlign [13] avoids any
quantizations and computes the values for each RoI with linear interpolation.
To establish accurate correspondences among multiple frames given a large
motion for video restoration, TDAN [42] and EDVR [43] achieve implicit motion
compensation with by deformable convolution [10] at the feature level.
AlignSeg [17] and SFNet [22] are two concurrent works that share a similar
motivation as ours and both are flow-based alignment methods. In particular,
AlignSeg proposes a two-branched bottom-up network and uses two types of
alignment modules to alleviate the feature misalignment before feature
aggregation. In contrast, we propose to construct a top-down pathway based on
the bottom-up network and align features from the coarsest resolution (top) to
the finest resolution (bottom) in a progressive way. Specifically, we only
align $2\times$ upsampled features to their corresponding bottom-up features,
while AlignSeg tries to align diversely scaled features (_i.e_. upsampled from
$1/4$, $1/8$, and even $1/16$) directly which are difficult and may not always
be feasible.

Figure 3: Overview comparison between FPN and FaPN. Details of the FAM and FSM
components are provided in Figure 4 and Figure 5, respectively.

##  3 Feature-aligned Pyramid Network

In this section, we present the general framework of our method, comprised of
a Feature Selection Module (FSM) and a Feature Alignment Module (FAM), as
shown in Figure 3 (_right_). Specifically, we define the output of the $i$-th
stage of the bottom-up network as $\mathbf{C}_{i}$, which has stride of
$2^{i}$ pixels with respect to the input image, _i.e_.
$\mathbf{C}_{i}\in\mathbb{R}^{\frac{H}{2^{i}}\times\frac{W}{2^{i}}}$, where
$H\times W$ is the size of the input image. And we denote
($\frac{H}{2^{i}},\frac{W}{2^{i}}$) by ($H_{i},W_{i})$ for brevity. We use
$\mathbf{\hat{C}}_{i}$ to denote the output of a FSM layer given the input of
$\mathbf{C}_{i}$. Also, the output after the $i$-th feature fusion in the top-
down pathway is defined as $\mathbf{P}_{i}$, and its upsampled and aligned
features to $\mathbf{C}_{i-1}$ as $\mathbf{P}_{i}^{u}$ and
$\mathbf{\hat{P}}_{i}^{u}$, respectively.

###  3.1 Feature Alignment Module

Due to the recursive use of downsampling operations, there are foreseeable
spatial misalignment between the upsampled feature maps $\mathbf{P}^{u}_{i}$
and the corresponding bottom-up feature maps $\mathbf{C}_{i-1}$. Thus, the
feature fusion by either element-wise addition or channel-wise concatenation
would harm the prediction around object boundaries. Prior to feature
aggregation, aligning $\mathbf{P}^{u}_{i}$ to its reference
$\mathbf{\hat{C}}_{i-1}$ is essential, _i.e_. adjusting $\mathbf{P}^{u}_{i}$
accordingly to the spatial location information provided by the
$\mathbf{\hat{C}}_{i-1}$. In this work, the spatial location information is
presented by 2D feature maps, where each offset value can be viewed as the
shifted distances in 2D space between each point in $\mathbf{P}^{u}_{i}$ and
its corresponding point in $\mathbf{\hat{C}}_{i-1}$. As illustrated by Figure
4, the feature alignment can be mathematically formulated as:

$\begin{split}\mathbf{\hat{P}}^{u}_{i}&=f_{a}\big{(}\mathbf{P}^{u}_{i},\mathbf{\Delta}_{i}\big{)},\\\
\mathbf{\Delta}_{i}&=f_{o}\big{(}[\mathbf{\hat{C}}_{i-1},\mathbf{P}_{i}^{u}]\big{)},\end{split}$
(1)

where $[\mathbf{\hat{C}}_{i-1},\mathbf{P}_{i}^{u}]$ is the concatenation of
$\mathbf{\hat{C}}_{i-1}$ and $\mathbf{P}_{i}^{u}$ which provides spatial
difference between the upsampled and corresponding bottom-up features.
$f_{o}(\cdot)$ and $f_{a}(\cdot)$ denote the functions for learning offsets
($\mathbf{\Delta_{i}}$) from the spatial differences and aligning feature with
the learned offsets, respectively. In this work, $f_{a}(\cdot)$ and
$f_{o}(\cdot)$ are implemented using deformable convolutions [10, 54],
followed by activation and standard convolutions of the same kernel size.

Figure 4: Feature Alignment Module. The offset fields have the same spatial
resolution with the input and 2$N$ channels corresponding to $N$ 2D offsets.
Specifically, $N$ denotes a convolutional kernel of $N$ sample locations,
_e.g_. $N$ is equal to 9 for a $3\times 3$ conv, and each value in the $n$-th
offset filed is the horizontal or vertical offset for the $n$-th sample point.

Here, we briefly review the deformable convolution [10], and then explain why
it can be used as our feature alignment function and provide some important
implementation details. We first define an input feature map
$\mathbf{c}_{i}\in\mathbb{R}^{H_{i}\times W_{i}}$ and a $k\times k$ conv
layer. Then, the output feature at any position $\hat{x}_{\mathbf{p}}$111where
$\mathbf{p}\in\\{(0,0),(1,0),(0,1),\ldots,(H_{i}-1,W_{i}-1)\\}$ after the
convolutional kernel can be obtained by

$\displaystyle\hat{x}_{\mathbf{p}}=\sum_{n=1}^{N}w_{n}\cdot
x_{\mathbf{p}+\mathbf{p}_{n}},$ (2)

where $N$ is the size of the $k\times k$ convolutional layer (_i.e_.
$N=k\times k$), $w_{n}$ and $\mathbf{p}_{n}$
$\in\\{(-\lfloor\frac{k}{2}\rfloor,-\lfloor\frac{k}{2}\rfloor),(-\lfloor\frac{k}{2}\rfloor,0),\ldots,(\lfloor\frac{k}{2}\rfloor,\lfloor\frac{k}{2}\rfloor)\\}$
refer to the weight and the pre-specified offset for the $n$-th convolutional
sample location, respectively. In addition to the pre-specified offsets, the
deformable convolution tries to learn additional offsets
$\\{\Delta\mathbf{p}_{1},\Delta\mathbf{p}_{2},...,\Delta\mathbf{p}_{N}\\}$
adaptively for different sample locations, and Equation (2) can be
reformulated as

$\displaystyle\hat{x}_{\mathbf{p}}=\sum_{n=1}^{N}w_{n}\cdot
x_{\mathbf{p}+\mathbf{p}_{n}+\Delta\mathbf{p}_{n}},$ (3)

where each $\Delta\mathbf{p}_{n}$ is a tuple $(h,w)$, with
$h\in(-H_{i},H_{i})$ and $w\in(-W_{i},W_{i})$.

When we apply the deformable convolution over the $\mathbf{P}^{u}_{i}$ and
take the concatenation of $\mathbf{\hat{C}}_{i-1}$ and $\mathbf{P}_{i}^{u}$ as
the reference (_i.e_. offset fields
$\mathbf{\Delta}_{i}=f_{o}\big{(}[\mathbf{\hat{C}}_{i-1},\mathbf{P}_{i}^{u}]\big{)}$),
the deformable convolution can adjust its convolutional sample locations
following the offsets following Equation (1)222Following the convention of the
deformable convolution, this study adopts $3\times 3$ as the kernal size for
$f_{a}(\cdot)$ and $f_{o}(\cdot)$., _i.e_. aligning $\mathbf{P}^{u}_{i}$
according to the spatial distance between $\mathbf{\hat{C}}_{i-1}$ and
$\mathbf{P}^{u}_{i}$.

###  3.2 Feature Selection Module

Prior to channel reduction for detailed features, it is vital to emphasize the
important feature maps that contain excessive spatial details for accurate
allocations while suppressing redundant feature maps. Instead of simply using
a $1\times 1$ convolution [24], we propose a feature selection module (FSM) to
explicitly model the importance of feature maps and re-calibrate them
accordingly.

Figure 5: Feature Selection Module. $\mathbf{C}_{i}$ = [$\mathbf{c}_{1}$,
$\mathbf{c}_{2}$, …, $\mathbf{c}_{D}$] and $\mathbf{\hat{C}}_{i}$ =
[$\mathbf{\hat{c}}_{1}$, $\mathbf{\hat{c}}_{2}$, …,
$\mathbf{\hat{c}}_{D^{\prime}}$] refer to the input and output feature maps
respectively, where $\mathbf{c_{d}}$ and $\mathbf{\hat{c}_{d^{\prime}}}$
$\in\mathbb{R}^{H_{i}\times W_{i}}$, $D$ and $D^{\prime}$ denote the input and
output channels, respectively. $\mathbf{u}$ = [$u_{1}$, $u_{2}$, …, $u_{D}$]
is the feature importance vector, where $u_{d}$ represents the importance of
the $d$-th input feature map. $f_{m}$ and $f_{s}$ represent the feature
importance modeling and feature selection layer, respectively. See text for
details.

The general dataflow of the proposed FSM is presented in Figure 5. To begin
with, the global information $\mathbf{z}_{i}$ of each input feature map
$\mathbf{c}_{i}$ is extracted by a global average pooling operation, while a
feature importance modeling layer $f_{m}(\cdot)$ (_i.e_. a $1\times 1$ conv
layer followed by a sigmoid activation function) learns to use such
information for modeling the importance of each feature map and outputs an
importance vector $\mathbf{u}$. Next, the original input feature maps are
scaled with the importance vector, and then the scaled feature maps are added
to the original feature maps, referred as rescaled feature maps. Finally, a
feature selection layer ${f}_{s}(\cdot)$ (_i.e_. a $1\times 1$ conv layer for
efficiency) is introduced over the rescaled feature maps, which is used to
selectively maintain important feature maps and drop useless feature maps for
channel reduction. Overall, the process of FSM can be formulated as

$\begin{split}\mathbf{\hat{C}}_{i}&=f_{s}(\mathbf{C}_{i}+\mathbf{u}\ast\mathbf{C}_{i}),\\\
\mathbf{u}&=f_{m}(\mathbf{z}),\end{split}$ (4)

where $\mathbf{z}$ = [$z_{1}$, $z_{2}$, …, $z_{D}$] and is calculated by

$\displaystyle z_{d}=\frac{1}{H_{i}\times
W_{i}}\sum_{h=1}^{H_{i}}\sum_{w=1}^{W_{i}}c_{d}(h,w).$ (5)

It is worth mentioning that the design of our FSM is motivated by the squeeze-
and-excitation (SE) [16]. The main difference lies in the additional skip
connection introduced between the input and scaled feature maps (Figure 5).
Empirically, we find that lower bounding the scaled feature (through the skip
connection) is essential, which avoids any particular channel responses to be
over-amplified or -suppressed. Conceptually, both of these two modules learn
to adaptively re-calibrate channel-wise responses by channel attention.
However, SE is conventionally used in the backbone for enhancing feature
extraction, while FSM is used in the neck (_i.e_. top-down pathway) for
enhancing multi-scale feature aggregation. Additionally, the selected/scaled
features from FSM are also supplied as references to FAM for learning
alignment offsets.

##  4 Experiments

In this section, we first briefly introduce the benchmark datasets studied in
this work, followed by the implementation and training details. We then
evaluate the performance of the proposed FaPN on four dense image prediction
tasks, including object detection, semantic, instance and panoptic
segmentation. Ablation studies demonstrating the effectiveness of each
component in FaPN are also provided. Moreover, we incorporate our proposed
FaPN with lightweight backbones and evaluate its efficacy under real-time
settings.

Datasets: We consider four widely-used benchmark datasets to evaluate our
method, including MS COCO [25] for object detection, instance and panoptic
segmentation; Cityscapes [9], COCO-Stuff-10K [3] and ADE20K [53] for semantic
segmentation.

MS COCO consists of more than 100K images containing diverse objects and
annotations, including both bounding boxes and segmentation masks. We use the
_train2017_ set (around 118K images) for training and report results on the
_val2017_ set (5K images) for comparison. For both object detection and
instance segmentation tasks, there are 80 categories; and for panoptic
segmentation task, there are 80 things and 53 stuff classes annotated.

Cityscapes is a large-scale dataset for semantic understanding of urban street
scenes. It is split into training, validation and test sets, with 2975, 500
and 1525 images, respectively. The annotation includes 30 classes, 19 of which
are used for semantic segmentation task. The images in this dataset have a
higher and unified resolution of $1024\times 2048$, which poses stiff
challenges to the task of real-time semantic segmentation. For the experiments
shown in this part, we only use images with fine annotations to train and
validate our proposed method.

COCO-Stuff-10K contains a subset of 10K images from the COCO dataset [25] with
dense stuff annotations. It is a challenging dataset for semantic segmentation
as it has 182 categories (91 thing classes plus 91 stuff classes). In this
work, we follow the official split – 9K images for training and 1K images for
test.

ADE20K is a challenging scene parsing dataset that contains 20k images for
training and 2k images for validation. Images in the dataset are densely
labeled as hundreds of classes. In this work, only 150 semantic categories are
selected to be included in the evaluation.

Implementation details: Following the original work of FPN [24], we use
ResNets [15] pre-trained on ImageNet [11] as the backbone ConvNets for the
bottom-up pathway. We then replace the FPN with our proposed FaPN as the top-
down pathway network. Next, we connect the feature pyramid with the Faster
R-CNN detector [41] for object detection, and Mask R-CNN (with PointRend
masking head [21]) for segmentation tasks.

For performance evaluation, the Average Precision (AP) is used as the primary
metric for both object detection and instance segmentation. We evaluate AP on
small, medium and large objects, _i.e_. APs, APm, and APl. Note that APbb and
APmask denote AP for bounding box and segmentation mask, respectively. The
mean Intersection-over-Union (mIoU) and the Panoptic Quality (PQ) are two
primary metrics used for semantic and panoptic segmentation, respectively.
Additionally, we also use PQSt and PQTh metrics to evaluate stuff and thing
performances separately for panoptic segmentation.

###  4.1 Ablation Study

We first breakdown the individual impacts of the two components introduced in
FaPN, _i.e_. the feature alignment and selection modules. Using ResNet50 as
the bottom-up backbone, we evaluate on Cityscapes for semantic segmentation.
Table 1 shows the improvement in accuracy along with the complexity overheads
measured in #Params.

Table 1: Ablative Analysis: Comparing the performance of our FaPN with other
variants on Cityscapes for semantic segmentation. $\dagger$ denotes placing
FAM after feature fusion. “deconv” refers to the deconvolution which is a
learnable upsample operation. The relative improvements/overheads are shown in
parenthesis.

method | backbone | #Params (M) | mIoU (%)
---|---|---|---
FPN | R50 | 28.6 (+4.5) | 77.4 (+2.6)
FPN + extra 3$\times$3 conv. | R50 | 33.4 (-0.3) | 77.5 (+2.5)
FPN | R101 | 47.6 (-14.5) | 78.9 (+1.1)
FPN + FAM | R50 | 31.7 (+1.4) | 79.7 (+0.3)
FPN + FAM + SE | R50 | 33.1 (+0.0) | 78.8 (+1.2)
lightgray!60 FPN + FAM + FSM (FaPN) | R50 | 33.1 (+0.0) |  80.0 (+0.0)
FPN + deconv + FSM | R50 | 32.7 (+0.4) | 76.7 (+3.3)
FPN + FAM† \+ FSM | R50 | 32.7 (+0.4) | 79.3 (+0.7)

Evidently, with marginal increments in model size, our proposed feature
alignment module alone significantly boosts the performance of the original
FPN [24], yielding an improvement of 2.3 points in mIoU. In particular, our
method<EMAIL_ADDRESS>is significantly more effective than naively expanding
either i) the #Params of FPN by extra 3$\times$3 conv<EMAIL_ADDRESS>or ii)
the capacity of the backbone from R50 to R101 (_78.9@47.6M_). Empirically, we
observe that a naive application of SE [16] (for feature selection) adversely
affects the performance, while our proposed FSM provides a further boost in
mIoU.

Recall that the _misalignment_ in this work refers to the spatial misalignment
of features induced during the aggregation of multi-resolution feature maps
(i.e., top-down pathway in FPN), particularly around object boundaries. One
plausible cause relates to the non-learnable nature of commonly-used
upsampling operations (e.g., bilinear). However, simply swapping it to a
learnable operation (e.g., deconvolution) is insufficient, suggesting the need
of better engineered methods. This reinforces the motivation of this work.
Instead of performing the feature alignment before feature fusion, we place
our FAM after feature fusion, in which our FAM learns the offsets from the
fused features instead. Although this variation performs better than all other
variants, it is still substantially worse than the proposed FaPN, which
reiterate the necessity of feature alignment before fusion.

###  4.2 Boundary Prediction Analysis

We provide the mIoU over the boundary pixels333we consider $n$ pixels around
the outline of each object to be boundary pixels, where $n$ can be one of [3,
5, 8, 12]. in Table 2. Evidently, our method achieves a substantially better
segmentation performance than FPN on boundaries. Moreover, we visualize the
input (upsampled features $P^{u}_{2}$) to and the output (aligned features
$\hat{P}^{u}_{2}$) from the last feature alignment module in FaPN-R50 (Figure
6) to perceive the alignment corrections made by our FAM. In contrast to the
raw upsampled features (before FAM) which are noisy and fluctuating, the
aligned features are smooth and containing more precise object boundaries.
Both the quantitative evaluation and qualitative observation are consistent
and suggest that FaPN leads to better predictions on the boundaries. More
visualizations are provided in Figure 2.

Table 2: Segmentation Performance around Boundaries: Comparing the performance
of our FaPN with the original FPN [24] in terms of mIoU over boundary pixels
on Cityscape _val_ with different thresholds on boundary pixels.

method | backbone | 3px | 5px | 8px | 12px | mean
---|---|---|---|---|---|---
FPN | PointRend [21] | 46.9 | 53.6 | 59.3 | 63.8 | 55.9
FaPN | R50 | 49.2 | 56.2 | 62.0 | 66.4 | 58.5
_improvement_ |  lightgray!60(_+2.3_) |  lightgray!60(_+2.6_) |  lightgray!60(_+2.7_) |  lightgray!60(_+2.6_) |  lightgray!60(_+2.6_)
FPN | PointRend [21] | 47.8 | 54.6 | 60.5 | 64.9 | 57.0
FaPN | R101 | 50.1 | 57.1 | 62.9 | 67.2 | 59.3
_improvement_ |  lightgray!60(_+2.3_) |  lightgray!60(_+2.5_) |  lightgray!60(_+2.4_) |  lightgray!60(_+2.3_) |  lightgray!60(_+2.3_)

Figure 6: Visualization of the input (upsampled features) to and the output
(aligned features) from our FAM. Zoom in for better details.

###  4.3 Main Results

In this section, we present the detailed empirical comparisons to FPN [24] on
four dense prediction tasks, including object detection, semantic, instance
and panoptic segmentation in Table 3 \- 6, respectively.

In general, FaPN substantially outperforms FPN on all scenarios of tasks and
datasets. There are several detailed observations. First, FaPN improves the
primary evaluation metrics by 1.2 - 2.6 points over FPN on all four tasks with
ResNet50 [15] as the bottom-up backbone. Second, the improvements brought by
FaPN hold for stronger bottom-top backbones (e.g. ResNet101 [15]) with a
longer training schedule of 270K iterations. Third, the improvement from FaPN
extends to more sophisticated mask heads, _e.g_. PointRend [21], on instance
segmentation, as shown in Table 5 (bottom section).

Figure 7: Example pairs of results comparing FPN [24] and our FaPN. Images are
randomly chosen from [25]. Best view in color and zoom in for details. Table
3: Object Detection: Performance comparisons on MS COCO _val_ set between FPN
and FaPN.

method | backbone | APbb | AP${}_{s}^{bb}$ | AP${}_{m}^{bb}$ | AP${}_{l}^{bb}$
---|---|---|---|---|---
FPN | Faster R-CNN [41] | 37.9 | 22.4 | 41.1 | 49.1
FaPN (ours) | R50 | 39.2 | 24.5 | 43.3 | 49.1
_improvement_ |  lightgray!60(_+1.3_) |  lightgray!60(_+2.1_) |  lightgray!60(_+2.2_) |  lightgray!60(_+0.0_)
FPN | Faster R-CNN [41] | 42.0 | 25.2 | 45.6 | 54.6
FaPN (ours) | R101 | 42.8 | 27.0 | 46.2 | 54.9
_improvement_ |  lightgray!60(_+0.8_) |  lightgray!60(_+1.8_) |  lightgray!60(_+0.6_) |  lightgray!60(_+0.3_)

Table 4: Semantic Segmentation: Performance comparisons on Cityscapes _val_
set between FPN and FaPN.

method | backbone | mIoU | iIoU | IoU_sup | iIoU_sup
---|---|---|---|---|---
FPN | PointRend [21] | 77.4 | 58.5 | 89.9 | 76.9
FaPN (ours) | R50 | 80.0 | 61.3 | 90.6 | 78.5
improvement |  lightgray!60(_+2.6_) |  lightgray!60(_+2.8_) |  lightgray!60(_+0.7_) |  lightgray!60(_+1.6_)
FPN | PointRend [21] | 78.9 | 59.9 | 90.4 | 77.8
FaPN (ours) | R101 | 80.1 | 62.2 | 90.8 | 78.6
improvement |  lightgray!60(_+1.2_) |  lightgray!60(_+2.3_) |  lightgray!60(_+0.4_) |  lightgray!60(_+0.8_)

Table 5: Instance Segmentation: Performance comparisons on MS COCO _val_ set
between FPN and FaPN.

method | backbone | APmask | AP${}^{mask}_{s}$ | APbb | AP${}^{bb}_{s}$
---|---|---|---|---|---
FPN | Mask R-CNN [13] | 35.2 | 17.1 | 38.6 | 22.5
FaPN (ours) | R50 | 36.4 | 18.1 | 39.8 | 24.3
_improvement_ |  lightgray!60(+1.2) |  lightgray!60(+1.0) |  lightgray!60(+1.2) |  lightgray!60(+1.8)
FPN | Mask R-CNN [13] | 38.6 | 19.5 | 42.9 | 26.4
FaPN (ours) | R101 | 39.6 | 20.9 | 43.8 | 27.4
_improvement_ |  lightgray!60(+1.0) |  lightgray!60(+1.4) |  lightgray!60(+0.9) |  lightgray!60(+1.0)
FPN | PointRend [21] | 36.2 | 17.1 | 38.3 | 22.3
FaPN + PR (ours) | R50 | 37.6 | 18.6 | 39.4 | 24.2
_improvement_ |  lightgray!60(+1.4) |  lightgray!60(+1.5) |  lightgray!60(+1.1) |  lightgray!60(+1.9)

Table 6: Panoptic Segmentation: Performance comparisons on MS COCO _val_ set
between FPN and FaPN.

method | backbone | PQ | mIoU | PQSt | APbb | PQTh
---|---|---|---|---|---|---
FPN | PanopticFPN [19] | 39.4 | 41.2 | 29.5 | 37.6 | 45.9
FaPN (ours) | R50 | 41.1 | 43.4 | 32.5 | 38.7 | 46.9
improvement |  lightgray!60(+1.7) |  lightgray!60(+2.2) |  lightgray!60(+3.0) |  lightgray!60(+0.9) |  lightgray!60(+1.0)
FPN | PanopticFPN [19] | 43.0 | 44.5 | 32.9 | 42.4 | 49.7
FaPN (ours) | R101 | 44.2 | 45.7 | 35.0 | 43.0 | 50.3
improvement |  lightgray!60(+1.2) |  lightgray!60(+1.2) |  lightgray!60(+2.1) |  lightgray!60(+0.6) |  lightgray!60(+0.6)
FPN | PanopticFCN [23] | 41.1 | 79.8 | 49.9 | 30.2 | 41.4
FaPN (ours) | R50 | 41.8 | 80.2 | 50.5 | 30.8 | 42.0
improvement |  lightgray!60(+0.7) |  lightgray!60(+0.4) |  lightgray!60(+0.6) |  lightgray!60(+0.6) |  lightgray!60(+0.6)
FPN | PanopticFCN [23] | 42.7 | 80.8 | 51.4 | 31.6 | 43.9
FaPN (ours) | R50-600 | 43.5 | 81.3 | 52.1 | 32.3 | 53.5
improvement |  lightgray!60(+0.8) |  lightgray!60(+0.5) |  lightgray!60(+0.7) |  lightgray!60(+0.7) |  lightgray!60(+0.6)

In particular, we notice that the improvement is larger on small objects (e.g.
AP${}^{bb}_{s}$, AP${}^{mask}_{s}$). For instance, FaPN improves the bounding
box AP on small objects by 2.1 points and 1.8 points over FPN on MS COCO
object detection and instance segmentation, respectively. Conceptually, small
objects occupy fewer pixels in an image, and most of pixels are distributed
along the object boundaries. Hence, it is vital to be able to correctly
classify the boundaries for small objects. However, as features traverse the
top-bottom pathway through heuristics-based upsampling operations (_e.g_. FPN
uses nearest neighbor upsampling), shifts in pixels (_i.e_. misalignment) are
foreseeable and the amount of shifts will accumulate as the number of
upsampling steps increases. Hereby, the severity of the misalignment will
reach its maximum at the finest feature maps in the top-down pathway pyramid,
which are typically used for detecting or segmenting small objects, resulting
in a significant degradation in performance. On the other hand, FaPN performs
feature alignment progressively which in turn alleviates the misalignment at
the finest level step by step, and thus achieves significant improvements on
small objects compared to the FPN [24]. Qualitative improvements are also
evidenced in Figure 7. Finally, we incorporate FaPN into MaskFormer [8], and
demonstrate that FaPN leads to state-of-the-art performance on two complex
semantic segmentation tasks, _i.e_. ADE20K and COCO-Stuff-10K, as shown in
Table 7.

Table 7: Comparison to SOTA on (a) ADE20K val and (b) COCO-Stuff-10K test. We
report both single-scale (s.s.) and multi-scale (m.s.) semantic segmentation
performance. Backbones pre-trained on ImageNet-22K are marked with
${}^{\text{\textdagger}}$. Our results are highlighted in shade.

(a) ADE20K val

method | backbone | crop size | mIoU (s.s.) | mIoU (m.s.)
---|---|---|---|---
OCRNet [50] | R101 | $520\times 520$ | - | 45.3
AlignSeg [17] | R101 | $512\times 512$ | - | 46.0
SETR [52] | ViT-L${}^{\text{\textdagger}}$ | $512\times 512$ | - | 50.3
Swin-UperNet [28] | Swin-L${}^{\text{\textdagger}}$ | $640\times 640$ | - | 53.5
MaskFormer [8] | Swin-L${}^{\text{\textdagger}}$ | $640\times 640$ | 54.1 | 55.6
lightgray!60 MaskFormer + FaPN | Swin-L${}^{\text{\textdagger}}$ | $640\times 640$ | 55.2 | 56.7

(b) COCO-Stuff-10K test

method | backbone | crop size | mIoU (s.s.) | mIoU (m.s.)
---|---|---|---|---
OCRNet [50] | R101 | $520\times 520$ | - | 39.5
MaskFormer [8] | $640\times 640$ | 38.1 | 39.8
lightgray!60 MaskFormer + FaPN | $640\times 640$ | 39.6 | 40.6

Overall, extensive comparisons on scenarios comprised of different tasks and
datasets have confirmed the effectiveness of our proposed FaPN for dense image
prediction. A straightforward replacement of FPN with FaPN achieves
substantial improvements without bells and whistles. The generality and
flexibility to different bottom-up backbones or mask heads have further
strengthened the practical utilities of FaPN.

###  4.4 Real-time Performance

Driven by real-world applications (_e.g_., autonomous driving), there are
growing interests in real-time dense prediction, which requires the generation
of high-quality predictions with minimal latency. In this section, we aim to
investigate the effectiveness of our proposed FaPN under real-time settings,
_i.e_. inference speed $\geq$ 30 FPS. The full details are provided in the
supplementary materials.

We compare our FaPN with state-of-the-art real-time semantic segmentation
methods on Cityscapes and COCO-Stuff-10K in Table 8, in terms of accuracy
(mIoU) and inference speed (FPS). In general, we observe that a
straightforward replacement of FPN with the proposed FaPN results in a
competitive baseline against other dedicated real-time semantic segmentation
methods.

In particular, on Cityspaces, FaPN-R18 runs 2$\times$ faster than SwiftNet
[39], while maintaining a similar mIoU performance. In addition, with a larger
backbone and input size, FaPN-R34 achieves a competitive mIoU of 78.1 points
on the _test_ split, in the same time outputting 30 FPS. On the more
challenging COCO-Stuff-10K, our FaPN also outperforms other existing methods
by a substantial margin. Specifically, FaPN-R34 outperforms BiSeNetV2 [48] in
both segmentation accuracy measured in mIoU and inference speed.

Table 8: Real-time semantic segmentation on (a) Cityscapes and (b) COCO-
Stuff-10K. $\dagger$ denotes a method with a customized backbone. Our results
are highlighted in shade.

(a) Cityscapes

method | backbone | crop size | FPS | mIoU (_val_) | mIoU (_test_)
---|---|---|---|---|---
ESPNet [36] | $\dagger$ | $512\times 1024$ | 113 | - | 60.3
ESPNetV2 [37] | $\dagger$ | $512\times 1024$ | - | 66.4 | 66.2
lightgray!40 FaPN | R18 | $512\times 1024$ | 142 | 69.2 | 68.8
BiSeNet [49] | R18 | $768\times 1536$ | 65.6 | 74.8 | 74.7
lightgray!50 FaPN | R18 | $768\times 1536$ | 78.1 | 75.6 | 75.0
SwiftNet [39] | R18 | $1024\times 2048$ | 39.9 | 75.4 | 75.5
ICNet [51] | R50 | $1024\times 2048$ | 30.3 | - | 69.5
lightgray!60 FAPN | R34 | $1024\times 2048$ | 30.2 | 78.5 | 78.1

(b) COCO-Stuff-10K

method | backbone | crop size | FPS | mIoU (_val_)
---|---|---|---|---
BiSeNet [49] | R18 | $640\times 640$ | - | 28.1
BiSeNetV2 [48] | $\dagger$ | 42.5 | 28.7
ICNet [51] | R50 | 35.7 | 29.1
lightgray!40 FaPN | R18 | 154 | 28.4
lightgray!60 FaPN | R34 | 110 | 30.3

##  5 Conclusion

This paper introduced _Feature-aligned Pyramid Network (FaPN)_ , a simple yet
effective top-down pyramidal architecture to generate multi-scale features for
dense image prediction. It is comprised of a feature alignment module that
learns transformation offsets of pixels to contextually align upsampled
higher-level features; and a feature selection module to emphasize the lower-
level features with rich spatial details. Empirically, FaPN leads to
substantial and consistent improvements over the original FPN on four dense
prediction tasks and three datasets. Furthermore, FaPN improves the state-of-
the-art segmentation performance when integrated in strong baselines.
Additionally, FaPN can be easily extended to real-time segmentation tasks by
pairing it with lightweight backbones, where we demonstrate that FaPN performs
favorably against dedicated real-time methods. In short, given the promising
performance on top of a simple implementation, we believe that FaPN can serve
as the new baseline/module for dense image prediction.

#### Acknowledgments:

This work was supported by the National Natural Science Foundation of China
(Grant No. 61903178, 61906081, and U20A20306) and the Program for Guangdong
Introducing Innovative and Enterpreneurial Teams (Grant No. 2017ZT07X386).

Appendix

In this supplementary material we include (1) additional training details in
Section A; (2) more details on the real-time semantic segmentation experiment
in Section B; and (3) additional qualitative visualizations to demonstrate the
effectiveness of the proposed FaPN in Section C.

##  Appendix A Training Settings

For all experiments shown in the main paper, we use SGD optimizer with 0.9
momentum and 0.0001 weight decay. The standard data augmentation of horizontal
flipping and scaling are also applied. In addition, the weights of the batch
normalization [18] layers derived from the ImageNet pre-trained models are
kept frozen. To be consistent with prior works, we have not incorporated any
testing time augmentation tricks. For semantic segmentation, the model is
trained for 65K iterations starting with a learning rate of 0.01 that is
reduced by a factor of 10 at 40K and 55K. For the other three dense prediction
tasks, the model is trained for 90K or 270K iterations with the initial
learning rate of 0.02 that is reduced to 0.002 at 60K/210K and 0.0002 at
80K/250K. Our implementation is based on the Detectron2 [47] with the default
configurations, _i.e_. to maintain a fair comparison with prior works, neither
have we tuned any training hyperparameters nor used advanced data
augmentations.

##  Appendix B Real-time Semantic Segmentation Continued

With a lightweight ResNet (_e.g_. ResNet18/34) as the bottom-up backbone, we
denote the feature maps output by the last three stages, _i.e_. conv3, conv4,
conv5, as $\left\\{\mathbf{C}_{3},\mathbf{C}_{4},\mathbf{C}_{5}\right\\}$,
respectively. At the beginning, we simply attach an FSM layer on
$\mathbf{C}_{5}$ to produce the coarsest resolution feature maps
$\mathbf{P}_{5}\in\mathbb{R}^{128\times\frac{H}{32}\times\frac{W}{32}}$
(_i.e_. the output channel of FSM is 128). With a coarser-resolution feature
map $\mathbf{P}_{i}$ ($l\in[4,5]$), we upsample its spatial resolution by a
factor of 2 using nearest neighbor upsampling [24] to obtain
$\mathbf{P}_{i}^{up}\in\mathbb{R}^{128\times\frac{H}{2^{i-1}}\times\frac{W}{2^{i-1}}}$.
Afterwards, an FAM layer is used to align $\mathbf{P}_{i}^{up}$ to its
corresponding bottom-up feature map
$\mathbf{\hat{C}}_{i-1}\in\mathbb{R}^{128\times\frac{H}{2^{i-1}}\times\frac{W}{2^{i-1}}}$
deriving from $\mathbf{C}_{i-1}$ by undergoing an FSM layer for channel
reduction. Instead of element-wise addition, the aligned
$\mathbf{\hat{P}}_{i}^{up}$ is then merged with $\mathbf{\hat{C}}_{i-1}$ by
concatenation along with channel, and the merged feature map
$\mathbf{P}_{i-1}\in\mathbb{R}^{256\times\frac{H}{2^{i-1}}\times\frac{W}{2^{i-1}}}$
which has the identical spatial size to $\mathbf{C}_{i-1}$ is further input in
a Conv $1\times 1$ layer to reduce its channels to 128. This process is
iterated until the finest resolution map
$\mathbf{P}_{3}\in\mathbb{R}^{128\times\frac{H}{8}\times\frac{W}{8}}$ is
generated. Finally, we append a prediction layer on $\mathbf{P}_{3}$ to
generate the final semantic mask.

We train our models using the SGD optimizer with momentum and weight decay set
to 0.9 and 0.0005, respectively. During training, we apply random horizontal
flip and scale to input images, followed by a crop to a fixed size. The scale
is randomly selected from $\left\\{0.75,1,1.25,1.5,1.75,2.0\right\\}$, and the
cropped resolutions are $1536\times 768$ and $640\times 640$ for Cityscapes
[9] and COCO-Stuff [3], respectively. For all datasets, we set the batch size
and the initial learning rate to 16 and 0.01, while the learning rate decays
following a “poly" strategy, specifically
$0.01\times(1-\frac{iter}{maxiters})^{0.9}$. Following the prior works [49,
48], we train models for 40K and 20K training iterations on Cityscapes and
COCO-Stuff, respectively. In the evaluation process, we compute the inference
speed using one Titan RTX GPU without any speed-up trick (_e.g_., Apex or
TensorRT) or optimized depth-wise convolutions, and evaluate the accuracy
without any testing augmentation technique (_e.g_., multi-crop or multi-scale
testing).

Table I: Ablation Study on Real-time Semantic Segmentation: Detailed
comparisons of each component in our proposed real-time semantic segmentation
FaPN over Citsycapes _val_ set in terms of accuracy, parameters and FLOPs
(computational complexity).

method | mIoU | #Params (M) | FLOPs (G)
---|---|---|---
FPN | 68.6 | 11.4 | 44.5
\+ FAM | 73.8 | 12.2 | 51.0
\+ FAM + FSM | 74.2 | 12.6 | 51.0
lightgray!60 \+ FAM + FSM + Concat | 75.6 | 12.6 | 51.8

We first demonstrate the effectiveness of each module in our proposed real-
time semantic segmentation framework separately and then study different
feature fusion methods on the Cityscapes _val_ set. We use ResNet18 pre-
trained on ImageNet as our backbone in the following ablation analysis.

The ablation experimental results are given in Table I. Basically, the
incorporation of FAM into the baseline improves the performance from 68.6% to
73.8%. Furthermore, FSM improves the performance to 74.2% with only 0.4$M$
additional parameters. Besides, when we replace the element-wise sum operation
with concatenation for fusing the detailed feature and aligned semantic
feature, another 1.4% improvement is achieved with few extra FLOPs.

Figure I visualizes the semantic segmentation results of FaPN on Cityscapes
under real-time settings (FPS $\geq$
30)444https://paperswithcode.com/sota/real-time-semantic-segmentation-on-
cityscapes. Noticeably, the proposed Feature Align Module (FAM; third column
in Figure I) significantly improves the segmentation quality from the baseline
(_i.e_. FPN; second column in Figure I). With the feature selection module and
feature concatenation, our final approach FaPN further improves the
performance on real-time semantic segmentation.

Figure I: Example visual comparisons among different approaches on the
Cityscapes _val_ set. From left to right: ground truths, results from
baseline, baseline with FAM and our FaPN, respectively. All models are using
ResNet18.

##  Appendix C Additional Visualization

Figure II and Figure III visualize the dense prediction performance on MS
COCO. Evidently, our method achieves a more accurate segmentation on object
boundaries and small objects.

Figure II:  Example pairs of instance segmentation results from FPN (_Left_)
and our FaPN (_Right_) on object boundaries. Both methods are implemented in
Mask R-CNN with ResNet-50 being the backbone and PointRend as the mask head.

Figure III:  Example results from methods with FPN or our FaPN on small
objects. In each group, from left to right, they are object detection,
instance and panoptic segmentation, the top is achieved by FPN while the
bottom by our FaPN. All models are based on ResNet50.

PointRend head

## References

  * [1] Hassan Abu Alhaija, Siva Karthik Mustikovela, Lars Mescheder, Andreas Geiger, and Carsten Rother.  Augmented reality meets computer vision: Efficient data generation for urban driving scenes.  IJCV, 2018.
  * [2] Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla.  SegNet: A deep convolutional encoder-decoder architecture for image segmentation.  TPAMI, 2017.
  * [3] Holger Caesar, Jasper Uijlings, and Vittorio Ferrari.  COCO-Stuff: Thing and stuff classes in context.  In CVPR, 2018.
  * [4] Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L Yuille.  Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs.  TPAMI, 2017.
  * [5] Liang-Chieh Chen, George Papandreou, Florian Schroff, and Hartwig Adam.  Rethinking atrous convolution for semantic image segmentation.  arXiv:1706.05587, 2017.
  * [6] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  In ECCV, 2018.
  * [7] Xiaozhi Chen, Kaustav Kundu, Ziyu Zhang, Huimin Ma, Sanja Fidler, and Raquel Urtasun.  Monocular 3d object detection for autonomous driving.  In CVPR, 2016.
  * [8] Bowen Cheng, Alexander G Schwing, and Alexander Kirillov.  Per-pixel classification is not all you need for semantic segmentation.  arXiv preprint arXiv:2107.06278, 2021.
  * [9] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In CVPR, 2016.
  * [10] Jifeng Dai, Haozhi Qi, Yuwen Xiong, Yi Li, Guodong Zhang, Han Hu, and Yichen Wei.  Deformable convolutional networks.  In ICCV, 2017.
  * [11] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In CVPR, 2009.
  * [12] Cheng-Yang Fu, Wei Liu, Ananth Ranga, Ambrish Tyagi, and Alexander C Berg.  Dssd: Deconvolutional single shot detector.  arXiv:1701.06659, 2017.
  * [13] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask R-CNN.  In ICCV, 2017.
  * [14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [16] Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-excitation networks.  In CVPR, 2018.
  * [17] Zilong Huang, Yunchao Wei, Xinggang Wang, Humphrey Shi, Wenyu Liu, and Thomas S Huang.  Alignseg: Feature-aligned segmentation networks.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021\.
  * [18] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  arXiv:1502.03167, 2015.
  * [19] Alexander Kirillov, Ross Girshick, Kaiming He, and Piotr Dollár.  Panoptic feature pyramid networks.  In CVPR, 2019.
  * [20] Alexander Kirillov, Kaiming He, Ross Girshick, Carsten Rother, and Piotr Dollár.  Panoptic segmentation.  In CVPR, 2019.
  * [21] Alexander Kirillov, Yuxin Wu, Kaiming He, and Ross Girshick.  PointRend: Image segmentation as rendering.  In CVPR, 2020.
  * [22] Xiangtai Li, Ansheng You, Zhen Zhu, Houlong Zhao, Maoke Yang, Kuiyuan Yang, Shaohua Tan, and Yunhai Tong.  Semantic flow for fast and accurate scene parsing.  In ECCV, 2020.
  * [23] Yanwei Li, Hengshuang Zhao, Xiaojuan Qi, Liwei Wang, Zeming Li, Jian Sun, and Jiaya Jia.  Fully convolutional networks for panoptic segmentation.  In CVPR, 2021.
  * [24] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In CVPR, 2017.
  * [25] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In ECCV, 2014.
  * [26] Shu Liu, Lu Qi, Haifang Qin, Jianping Shi, and Jiaya Jia.  Path aggregation network for instance segmentation.  In CVPR, 2018.
  * [27] Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng-Yang Fu, and Alexander C Berg.  Ssd: Single shot multibox detector.  In ECCV, 2016.
  * [28] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  arXiv preprint arXiv:2103.14030, 2021.
  * [29] Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  In CVPR, 2015.
  * [30] Zhichao Lu, Kalyanmoy Deb, and Vishnu N. Boddeti.  MUXConv: Information multiplexing in convolutional neural networks.  In CVPR, 2020.
  * [31] Zhichao Lu, Kalyanmoy Deb, Erik Goodman, Wolfgang Banzhaf, and Vishnu Naresh Boddeti.  NSGANetV2: Evolutionary multi-objective surrogate-assisted neural architecture search.  In ECCV, 2020.
  * [32] Zhichao Lu, Gautam Sreekumar, Erik Goodman, Wolfgang Banzhaf, Kalyanmoy Deb, and Vishnu N. Boddeti.  Neural architecture transfer.  TPAMI, 2021.
  * [33] Zhichao Lu, Ian Whalen, Vishnu Boddeti, Yashesh Dhebar, Kalyanmoy Deb, Erik Goodman, and Wolfgang Banzhaf.  NSGA-Net: Neural architecture search using multi-objective genetic algorithm.  In GECCO, 2019.
  * [34] Zhichao Lu, Ian Whalen, Yashesh Dhebar, Kalyanmoy Deb, Erik Goodman, Wolfgang Banzhaf, and Vishnu N. Boddeti.  Multiobjective evolutionary design of deep convolutional neural networks for image classification.  TEVC, 2021.
  * [35] Davide Mazzini.  Guided upsampling network for real-time semantic segmentation.  arXiv:1807.07466, 2018.
  * [36] Sachin Mehta, Mohammad Rastegari, Anat Caspi, Linda Shapiro, and Hannaneh Hajishirzi.  Espnet: Efficient spatial pyramid of dilated convolutions for semantic segmentation.  In ECCV, 2018.
  * [37] Sachin Mehta, Mohammad Rastegari, Linda Shapiro, and Hannaneh Hajishirzi.  Espnetv2: A light-weight, power efficient, and general purpose convolutional neural network.  In CVPR, 2019.
  * [38] Hyeonwoo Noh, Seunghoon Hong, and Bohyung Han.  Learning deconvolution network for semantic segmentation.  In ICCV, 2015.
  * [39] Marin Orsic, Ivan Kreso, Petra Bevandic, and Sinisa Segvic.  In defense of pre-trained imagenet architectures for real-time semantic segmentation of road-driving images.  In CVPR, 2019.
  * [40] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  In CVPR, 2016.
  * [41] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster R-CNN: Towards real-time object detection with region proposal networks.  In NeurIPS, 2015.
  * [42] Yapeng Tian, Yulun Zhang, Yun Fu, and Chenliang Xu.  Tdan: Temporally-deformable alignment network for video super-resolution.  In CVPR, 2020.
  * [43] Xintao Wang, Kelvin CK Chan, Ke Yu, Chao Dong, and Chen Change Loy.  Edvr: Video restoration with enhanced deformable convolutional networks.  In CVPR Workshops, 2019.
  * [44] Xinlong Wang, Tao Kong, Chunhua Shen, Yuning Jiang, and Lei Li.  SOLO: Segmenting objects by locations.  In ECCV, 2020.
  * [45] Xiaosong Wang, Yifan Peng, Le Lu, Zhiyong Lu, Mohammadhadi Bagheri, and Ronald M Summers.  Chestx-ray8: Hospital-scale chest x-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases.  In CVPR, 2017.
  * [46] Xinlong Wang, Rufeng Zhang, Tao Kong, Lei Li, and Chunhua Shen.  Solov2: Dynamic and fast instance segmentation.  NeurIPS, 2020.
  * [47] Yuxin Wu, Alexander Kirillov, Francisco Massa, Wan-Yen Lo, and Ross Girshick.  Detectron2.  https://github.com/facebookresearch/detectron2, 2019.
  * [48] Changqian Yu, Changxin Gao, Jingbo Wang, Gang Yu, Chunhua Shen, and Nong Sang.  Bisenet v2: Bilateral network with guided aggregation for real-time semantic segmentation.  arXiv:2004.02147, 2020.
  * [49] Changqian Yu, Jingbo Wang, Chao Peng, Changxin Gao, Gang Yu, and Nong Sang.  Bisenet: Bilateral segmentation network for real-time semantic segmentation.  In ECCV, 2018.
  * [50] Yuhui Yuan, Xilin Chen, and Jingdong Wang.  Object-contextual representations for semantic segmentation.  In ECCV, 2020.
  * [51] Hengshuang Zhao, Xiaojuan Qi, Xiaoyong Shen, Jianping Shi, and Jiaya Jia.  Icnet for real-time semantic segmentation on high-resolution images.  In ECCV, 2018.
  * [52] Sixiao Zheng, Jiachen Lu, Hengshuang Zhao, Xiatian Zhu, Zekun Luo, Yabiao Wang, Yanwei Fu, Jianfeng Feng, Tao Xiang, Philip HS Torr, et al.  Rethinking semantic segmentation from a sequence-to-sequence perspective with transformers.  In CVPR, 2021.
  * [53] Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba.  Scene parsing through ade20k dataset.  In CVPR, 2017.
  * [54] Xizhou Zhu, Han Hu, Stephen Lin, and Jifeng Dai.  Deformable convnets v2: More deformable, better results.  In CVPR, 2019.