\begin{equation}}
\def\ee{\end{equation}}
\def\bea{\begin{eqnarray}}
\def\eea{\end{eqnarray}}
\newcommand{\dd}{\mathrm{d}}
\newcommand{\LL}{\mathcal{L}}
\newcommand{\DD}{\mathcal{D}}

\title{Eigenvalue repulsions in the quasinormal spectra of the Kerr-Newman black hole}

% For the moment, in alphabetical order

\author{\'Oscar J.~C.~Dias}
\affiliation{STAG research centre and Mathematical Sciences, University of Southampton, UK}

\author{Mahdi Godazgar}
\affiliation{School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London E1 4NS, UK.}

\author{Jorge E.~Santos}
\affiliation{DAMTP, Centre for Mathematical Sciences,
University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom}

\author{Gregorio Carullo}
\affiliation{Dipartimento di Fisica ``Enrico Fermi'', Universit\`a di Pisa, Pisa I-56127, Italy}
\affiliation{INFN sezione di Pisa, Pisa I-56127, Italy}

\author{Danny Laghi}
\affiliation{Dipartimento di Fisica ``Enrico Fermi'', Universit\`a di Pisa, Pisa I-56127, Italy}
\affiliation{INFN sezione di Pisa, Pisa I-56127, Italy}
\affiliation{Laboratoire des 2 Infinis - Toulouse (L2IT-IN2P3), Universit\'e de Toulouse, CNRS, UPS, F-31062 Toulouse Cedex 9, France}

\author{Walter Del Pozzo}
\affiliation{Dipartimento di Fisica ``Enrico Fermi'', Universit\`a di Pisa, Pisa I-56127, Italy}
\affiliation{INFN sezione di Pisa, Pisa I-56127, Italy}

\begin{abstract}
We study the gravito-electromagnetic perturbations of the Kerr-Newman (KN) black hole metric and identify the two $-$  photon sphere and near-horizon $-$ families of quasinormal modes (QNMs) of the KN black hole, computing the frequency spectra (for all the KN parameter space) of the modes with the slowest decay rate. We uncover a novel phenomenon for QNMs that is unique to the KN system, namely eigenvalue repulsion between QNM families. Such a feature is common in solid state physics where \eg it is responsible for energy bands/gaps in the spectra of electrons moving in certain Schr\"odinger potentials.
Exploiting the enhanced symmetries of the near-horizon limit of the near-extremal KN geometry we also develop a matching asymptotic expansion that allows us to solve the perturbation problem using separation of variables and provides an excellent approximation to the KN QNM spectra near extremality.
The  KN QNM spectra here derived are required not only to account for the gravitational emission in astrophysical environments, such as the ones probed by LIGO, Virgo and LISA, but also allow to extract observational implications on several new physics scenarios, such as mini-charged dark-matter or certain modified theories of gravity, degenerate with the KN solution at the scales of binary mergers.
\end{abstract}

\maketitle

\emph{\bf  Introduction.}

The black hole (BH) uniqueness theorems single out the Kerr-Newman (KN) metric as the most
general regular, stationary and asymptotically flat electro-vacuum solution of Einstein-Maxwell’s equations~[\citenamefont{Mazur}, 2000].
Nevertheless, astrophysical BHs are not expected to be able to retain a significant amount of electric charge~[\citenamefont{Gibbons}, 1975, \citenamefont{Blandford and Znajek}, 1977].
Consequently, all LIGO-Virgo~[\citenamefont{Aasi et~al.}, 2015, \citenamefont{Acernese et~al.}, 2015] observations of events compatible with BH binaries~[\citenamefont{Abbott et~al.}, 2020] have been so far described
under the assumption that the merging objects can be modelled by the Kerr metric, the zero-charge limit of the KN solution.
Due to the lack of template models describing coalescing KN BHs (especially in the merger-ringdown regime),
the zero-charge assumption has not yet been verified in full on observational data,
although see Refs.~[\citenamefont{Gupta et~al.}, 2021, \citenamefont{Bozzola and Paschalidis}, 2020] for recent work in this direction.
Gravitational-waves (GWs) observations of BH mergers are now probing the largest curvature regimes ever reached,
enabling the experimental study of gravity in its strong-field and dynamical regime~[\citenamefont{Abbott et~al.}, 2020, \citenamefont{Abbott et~al.}, 2020]
and opening an observational window on potential unobserved gravitational phenomena.
Here, we further the characterisation of KN solutions by finding the full gravito-electromagnetic
quasinormal mode (QNM) spectrum of KN BHs. The determination of the QNM spectrum
requires solving a coupled system of two partial differential equations (PDEs) for two gauge invariant Newman-Penrose (NP) fields~[\citenamefont{Dias et~al.}, 2015] that,
upon gauge fixing, reduce to the PDE system originally found by Chandrasekhar~[\citenamefont{Chandrasekhar}, 1983, \citenamefont{Mark et~al.}, 2014].
Since the publication of Chandrasekhar's seminal work~[\citenamefont{Chandrasekhar}, 1983], despite several attempts,
this task has remained a major open problem in Einstein-Maxwell theory for the past 40 years.

Perturbative results in the small rotation parameter $a$~[\citenamefont{Pani et~al.}, 2013, \citenamefont{Pani et~al.}, 2013] and in small charge parameter
$Q$~[\citenamefont{Mark et~al.}, 2014] expansions about the Reissner-Nordstr\"om (RN) and Kerr backgrounds are available.
Ref.~[\citenamefont{Dias et~al.}, 2015] did a numerical search of KN modes that could eventually develop an instability but found none,
thus providing evidence for the linear mode stability of KN (further supported by the non-linear time evolution study of~[\citenamefont{Zilh\~ao et~al.}, 2014]).
In this Letter, motivated also by applications in both ground and space-based GW
detectors~[\citenamefont{Aasi et~al.}, 2015, \citenamefont{Acernese et~al.}, 2015, \citenamefont{Akutsu et~al.}, 2020, \citenamefont{Punturo et~al.}, 2010, \citenamefont{Reitze et~al.}, 2019, \citenamefont{Amaro-Seoane et~al.}, 2017], we instead identify all the gravito-electromagnetic QNM families of the KN
BH and compute the frequency spectra (across the full KN parameter space) of the most dominant modes, \ie the ones with slowest decay.
These are the modes that reduce $-$in Chandrasekhar's notation~[\citenamefont{Chandrasekhar}, 1983]$-$ to the $Z_2$, $\ell=m=2$, $n=0$ modes
in the Schwarzschild limit ($a=Q=0$), where the harmonic number $\ell$ gives the number of zeros of the eigenfunction along
the polar direction and $n$ is the radial overtone. Remarkably, we find that the KN frequency spectra $-$ unlike its $a=0$
and/or $Q=0$ limits $-$ are populated with intricate phenomena known as {\it eigenvalue repulsions}.
The observational applications of our results are not limited to modelling the GW emission in realistic astrophysical environments,
but include the possibility of constraining certain dark matter~[\citenamefont{{Cardoso} et~al.}, 2016] and modified gravity~[\citenamefont{Bozzola and Paschalidis}, 2020] models.
The full implications of these results to GW observations are explored in a companion paper~[\citenamefont{Carullo et~al.}, 2021].

\emph{\bf  Formulation of the problem.}
The KN BH solution can be described in standard Boyer-Lindquist coordinates $\{t,r,\theta,\phi\}$ (time, radial, polar, azimuthal coordinates)~[\citenamefont{Adamo and Newman}, 2014]. The Killing vector $K=\partial_t +\Omega_H \partial_\phi$ generates the event horizon with angular velocity $\Omega_H$ and temperature $T_H$. The event horizon location $r_+$ is the largest root of the function $\Delta$. In terms of the mass, rotation, and charge parameters $\{M,a,Q\}$, these quantities are:
\begin{eqnarray}\label{KNsol}
&&\hspace{-0.4cm} \Delta = r^2 -2Mr+a^2+Q^2,\ \  r_\pm=M\pm\sqrt{M^2-a^2-Q^2},  \nonumber \\
&&\hspace{-0.4cm}  \Omega_H= \frac{a}{r_+^2+a^2} \,, \qquad
T_H = \frac{1}{4 \pi  r_+}\frac{r_+^2-a^2-Q^2}{r_+^2+a^2 }.
\end{eqnarray}
At $r_-=r_+$, \ie  $a=a_{\hbox{\footnotesize ext}}=\sqrt{M^2-Q^2}$, the KN BH has a regular extremal (``ext") configuration with $T_H^{\hbox{\footnotesize ext}} =0$, and maximum angular velocity $\Omega_H^{\hbox{\footnotesize ext}} =a_{\hbox{\footnotesize ext}}/(M^2+a_{\hbox{\footnotesize ext}}^2)$.

Since $\partial_t,\partial_\phi$ are Killing vector fields of KN, its gravito-electromagnetic perturbations can be Fourier decomposed as $e^{-i \omega t} e^{i m \phi}$, where  $\omega$ and $m$ are the frequency and azimuthal quantum number of the mode. Using the NP formalism,~[\citenamefont{Dias et~al.}, 2015] derived a set of two coupled PDEs for two gauge invariant quantities $\psi_{-2}$ and $\psi_{-1}$ that describe the most general perturbations (except for trivial modes that shift the parameters of the solution) of a KN BH, namely:
\begin{eqnarray}\label{ChandraEqs}
&& \left(\mathcal{F}_{-2}+ Q^2 \mathcal{G}_{-2}\right) \psi_{-2}  + Q^2 \mathcal{H}_{-2}  \psi_{-1} =0 \,,  \nonumber\\
&& \left(\mathcal{F}_{-1} +Q^2 \mathcal{G}_{-1}\right)\psi_{-1} + Q^2  \mathcal{H}_{-1} \psi_{-2}=0  \,,
\end{eqnarray}
where the second order differential operators $\{\mathcal{F},\mathcal{G},\mathcal{H}\}$ are in Eq.\ \eqref{def:opsFGH} of the Supplemental Material. The gauge invariant (under diffeomorphisms and NP tetrad rotations) perturbed quantities $\psi_{-2}$ and $\psi_{-1}$ are a combination of NP scalars  $\Psi$'s and $\Phi$'s (see the Supplemental Material).
% which are relevant for the study of outgoing modes at future null infinity that are regular at the future horizon.Under gauge fixing, \eqref{ChandraEqs} reduces to the Chandrasekhar coupled PDE system for KN~[\citenamefont{Chandrasekhar}, 1983, \citenamefont{Mark et~al.}, 2014] and, when $Q\to0$, \eqref{ChandraEqs} decouple yielding the familiar Teukolsky equation~[\citenamefont{Teukolsky}, 1972].

To solve the coupled PDEs \eqref{ChandraEqs}, we need to impose physical boundary conditions.
At spatial infinity, we require only outgoing waves, and at the future event horizon, we keep only regular modes in ingoing Eddington-Finkelstein coordinates. Finally, we must require regularity at the North (South) pole $\theta =\pi\,(-\pi)$. See the Supplemental Material for more details.

A scaling symmetry of the system allows us to work with the adimensional parameters $\{\tilde{a},\tilde{Q},\tilde{\omega}\}\equiv \{a/M,Q/M,\omega M\}$ (or $\{\hat{a},\hat{Q},\hat{\omega}\}\equiv\{a/r_+,Q/r_+,\omega r_+\}$). The $t -\phi$ symmetry of KN means that we need only consider modes with  Re$(\omega)\geq 0$, as long as we study both signs of $m$ \footnote{When $a=0$ this enhances to a $t \to -t $ symmetry and the QNM frequencies form pairs of $\{\omega,-\omega^* \}$.}. To solve the PDE problem numerically, we use a pseudospectral method that searches directly for specific QNMs using a Newton-Raphson root-finding algorithm. We refer to the review~[\citenamefont{Dias et~al.}, 2016] and ~[\citenamefont{Dias et~al.}, 2009, \citenamefont{Dias et~al.}, 2010, \citenamefont{Dias et~al.}, 2010, \citenamefont{Dias et~al.}, 2010, \citenamefont{Dias et~al.}, 2011, \citenamefont{Dias et~al.}, 2010, \citenamefont{Dias et~al.}, 2012, \citenamefont{Cardoso et~al.}, 2014, \citenamefont{Dias et~al.}, 2014, \citenamefont{Dias et~al.}, 2018] for details. The exponential convergence of the method, and the use of quadruple precision, guarantee that the results are accurate up to, at least, the eighth decimal place.

\emph{\bf Analytical analysis and eigenvalue repulsion.}
There are regimes of the parameter space where the frequency of the QNMs can be well approximated by analytical formulae obtained from perturbation/WKB expansions.
This helps identify different families of QNMs. There are two main families of QNMs: 1) the {\it photon sphere} (PS), and 2) the {\it near-horizon} (NH) families. However, as we will find later,  this sharp distinction is unambiguous only for small values of the rotation parameter. In particular, we can see this clearly for the $a= 0$ Reissner-Nordstr\"om (RN) case, the imaginary part of the frequency spectra of which is shown in the left panel of Fig.~\ref{Fig:spectraFix-a} (in units of $r_+$ since some curves change too much in a small range of charge if we use units of $M$) \footnote{The frequency spectra in the left panel of Fig.~\ref{Fig:spectraFix-a} was obtained solving the coupled pair of KN PDEs and, independently, the Regge-Wheeler$-$Zerilli ODE~[\citenamefont{Regge and Wheeler}, 1957, \citenamefont{Zerilli}, 1974] that describes perturbations of RN. The fact that both match validates our numerics for the KN PDEs. See [\citenamefont{Berti et~al.}, 2009] for a detailed review on QNM studies of the RN and Kerr black holes.}. Letting $n=0,1,\cdots$ denote the radial overtone, the orange diamond and dark-red triangle curves describe the $n=0$ ($\mathrm{PS}_{0}$) and $n=1$ ($\mathrm{PS}_{1}$) PS families, respectively. And, the green circle and  blue square curves describe the $n=0$ ($\mathrm{NH}_{0}$) and $n=1$ ($\mathrm{NH}_{1}$) NH families. Focusing our attention on the families with slowest decay rate, the $\mathrm{PS}_{0}$ and $\mathrm{NH}_{0}$ curves intersect (simple crossover) at
$\hat{Q}= \hat{Q}_c^{\hbox{\tiny RN}} \simeq 0.959227$ ($\tilde{Q}\equiv \tilde{Q}_c^{\hbox{\tiny RN}} \simeq 0.9991342$). For  $0 \leq \hat{Q}<\hat{Q}_c^{\hbox{\tiny RN}}$, $\mathrm{PS}_{0}$ is the dominant QNM, while for $\hat{Q}_c^{\hbox{\tiny RN}} \leq \hat{Q}\leq 1$ it is the $\mathrm{NH}_{0}$ QNM that has smaller $|\mathrm{Im}\,\hat{\omega}|$.

\begin{figure*}
\includegraphics[width=.32\textwidth]{a0spectra.pdf}
\includegraphics[width=.32\textwidth]{a039spectra.pdf}
\includegraphics[width=.33\textwidth]{a096spectra.pdf}
\caption{QNM spectra for KN BHs with $a/a_{\hbox{\footnotesize ext}}=0$ (left), $0.39$ (middle) and $0.96$ (right). In the RN case, there is an unambiguous QNM family classification: the orange diamond (dark-red triangle) curve is the $n=0$ ($n=1$) PS family which reduces to the dark-red disk $\omega\, r_+=0.74734337 - 0.17792463\, i $ (red square $\omega \, r_+=0.69342199 - 0.54782975\, i$) in the Schwarzschild limit ~[\citenamefont{Chandrasekhar}, 1983, \citenamefont{Leaver}, 1985]. The green circle (blue square) curve is the $n=0$ ($n=1$) NH family (not shown: for $\hat{Q}<0.85$ these curves extend to lower $\mathrm{Im}\,\hat{\omega}$). In the middle and right panels one observes eigenvalue repulsions unique to the KN QNM spectra. On the left/right panels we also show the frequency  $\tilde{\omega}_{\hbox{\tiny NH}}^{\hbox{\tiny MAE}}$ given by \eqref{NH:freq} for $n=0$ (black solid curve) and for $n=1$ (magenta solid curve).
\label{Fig:spectraFix-a}
\end{figure*}

In the eikonal or geometric optics limit (the WKB limit $\ell\sim |m| \gg 1$) the PS QNM  frequencies  are known to be related to the properties of the equatorial plane unstable circular photon orbits.
The real and imaginary parts of the PS frequency are proportional to the Keplerian frequency $\Omega_c$  and to the Lyapunov exponent $\lambda_L$, respectively~[\citenamefont{{Goebel}}, 1972, \citenamefont{Ferrari and Mashhoon}, 1984, \citenamefont{Ferrari and Mashhoon}, 1984, \citenamefont{Mashhoon}, 1985, \citenamefont{Bombelli and Calzetta}, 1992, \citenamefont{Cornish and Levin}, 2003, \citenamefont{Cardoso et~al.}, 2009, \citenamefont{Dolan}, 2010, \citenamefont{Yang et~al.}, 2012, \citenamefont{Stuchlik and Calvani}, 1991].
%The real part of the PS frequency is proportional to the Keplerian frequency $\Omega_c$  and the imaginary part of the PS frequency is proportional to the Lyapunov exponent $\lambda_L$~[\citenamefont{{Goebel}}, 1972, \citenamefont{Ferrari and Mashhoon}, 1984, \citenamefont{Ferrari and Mashhoon}, 1984, \citenamefont{Mashhoon}, 1985, \citenamefont{Bombelli and Calzetta}, 1992, \citenamefont{Cornish and Levin}, 2003, \citenamefont{Cardoso et~al.}, 2009, \citenamefont{Dolan}, 2010, \citenamefont{Yang et~al.}, 2012, \citenamefont{Stuchlik and Calvani}, 1991].
The latter describes how quickly a null geodesic congruence around the orbit increases its cross section under radial deformations. In this limit, the PS frequencies are (see~[\citenamefont{Zimmerman and Mark}, 2016] and  [46])
\be\label{PS:eikonal}
\omega^{\hbox{\tiny eikn}}_{\hbox{\tiny PS}}  \simeq  \frac{m}{b_s} -i\,\frac{n+1/2}{b_s r_s^2}\,\frac{\left|r_s^2+a^2-a b_s\right|}{|b_s-a|\left(6 r_s^2+a^2-b_s^2\right) ^{-\frac{1}{2}}}\,,
\ee
where $r_s$ and $b_s$ are the radius and impact parameter of the unstable orbits defined implicitly in terms of  $M$, $Q$:
\be\label{PS:MQrsbs}
M=\frac{r_s \left(b_s^2-a^2-2 r_s^2\right)}{\left(b_s-a\right)^2}\,, \quad Q=\frac{r_s\sqrt{b_s^2-a^2-3 r_s^2}}{\sqrt{\left(b_s-a\right){}^2}}.
\ee
There are two real roots $r_s$ higher than $r_+$ which are in correspondence with two PS modes: the {\it co-rotating} one (with $m=\ell$) that maps to the eikonal orbit with radius $r_s=r_s^-$ and $b_s>0$ (and that has the lowest $|\mathrm{Im}\,\tilde{\omega}|$) and the {\it counter-rotating} mode with $m=-\ell$ which is in correspondence with the orbit with radius $r_s=r_s^+$ and $b_s<0$, with $r_s^+\geq r_s^- \geq r_+$. As a check, we find that \eqref{PS:eikonal} is in excellent agreement with the numerical data for $\ell=m=6$ (see  [46]), and it still gives a reasonable approximation when $\ell=m=2$. Altogether, this identifies the PS QNM family and validates our numerics.

Now let us discuss the NH family of QNMs. In the RN case (left panel of Fig.~\ref{Fig:spectraFix-a}),  this is the dominant QNM near extremality, \ie for $\hat{Q}_c^{\hbox{\tiny RN}} <\hat{Q}\leq 1$.
%We might thus expect this to be also the case when $\hat{a}\neq 0$, at least for small $\hat{a}$.
Near extremality, the RN and KN wavefunctions are very localized near the horizon and quickly decay to zero away from it. This suggests doing a  poor-man's matching asymptotic expansion (MAE), whereby we take the {\it near-horizon limit} of the perturbed equations \eqref{ChandraEqs} to find the near-region solution (which we solve analytically) and match with a {\it vanishing} far-region wavefunction in the overlapping region where both solutions are valid  \footnote{Ideally, we would also solve the far-region equations to obtain the sub-leading far-region solution but in the KN background we cannot do it analytically.}. In fact, motivated by the result that the near-horizon limit of the extremal KN BH corresponds to a warped circle fibred over $AdS_2$ (Anti-de Sitter)~[\citenamefont{Bardeen and Horowitz}, 1999], the perturbations of which can be decomposed as a sum of known radial  $AdS_2$ harmonics, we can use {\it separation of variables}.  Therefore, the system of 2 coupled PDEs for $\{\psi_{-2},\psi_{-1}\}$ separates into a system of 2 decoupled radial ordinary differential equations (ODEs) and a coupled system of 2 angular ODEs. This yields an analytical expression for the NH frequency (derivation is given in [46]):
\begin{equation}\label{NH:freq}
\tilde{\omega}_{\hbox{\tiny NH}}^{\hbox{\tiny MAE}} \simeq
\frac{m\tilde{a}}{1+\tilde{a}^2}
+\sigma \bigg[\frac{m \tilde{a}(1-\tilde{a}^2)}{2(1+ \tilde{a}^2)^2}-\frac{i}{4} \frac{1+2n}{1+ \tilde{a}^2}-\,\frac{\sqrt{-\lambda _2}}{4(1+\tilde{a}^2)^2}\bigg]
\end{equation}
where $n=0,1,2,\cdots$ is again the radial overtone,  $\tilde{a}=\tilde{a}_{\hbox{\footnotesize ext}}$, and the expansion is over the off-extremality parameter $\sigma=1-\frac{r_-}{r_+}$ up to $\mathcal{O}\left(\sigma^2\right)$. Here, $\lambda_2(m,\tilde{a}_{\hbox{\footnotesize ext}})$ is a separation constant that we find by solving numerically the aforementioned coupled system of two angular ODEs. In our conventions $\mathrm{Re}(\sqrt{z})>0$ and $\mathrm{Im}(\sqrt{z})>0$ when $z$ is positive and negative, respectively. Our initial derivation of \eqref{NH:freq} is valid for $\lambda_2>0$ but, motivated by the Kerr results reported in~[\citenamefont{Yang et~al.}, 2013, \citenamefont{Yang et~al.}, 2013],  we will use it also when $\lambda_2<0$. In a complementary manner, in the WKB limit $m\gg 1$, $\lambda_2$ is well approximated by
\be \label{NH:lambda2wkb}
\lambda_2^{\hbox{\tiny WKB}}=\lambda_{2,0}\,m^2+\lambda_{2,1}\,m+\lambda_{2,2}+\frac{\lambda_{2,3}}{m}+\mathcal{O}\left(1/m^2\right),
\ee
where the WKB coefficients $\lambda_{2,0},\cdots,\lambda_{2,4}$ are functions of $\tilde{a}$ given in Eq.\ \eqref{NH:WKBansatzCoef} of the Supplemental Material. At extremality ($\sigma=0$), \eqref{NH:freq} reduces to $\mathrm{Re}\, \tilde{\omega}=m \tilde{\Omega}_H^{\hbox{\footnotesize ext}}$ and $\mathrm{Im} \,\tilde{\omega}=0$, and in the Kerr and RN limits, it reduces to the expressions first found in ~[\citenamefont{Yang et~al.}, 2013, \citenamefont{Yang et~al.}, 2013] and~[\citenamefont{Zimmerman and Mark}, 2016], respectively.
\begin{figure*}
\includegraphics[width=.4\textwidth]{qnml2m2n0i.pdf}
\hspace{1.5cm}
\includegraphics[width=.38\textwidth]{qnml2m2n0r.pdf}
\caption{Imaginary (left panel) and real (right panel) parts of the frequency for the $Z_2$, $\ell=m=2, n=0$ KN QNM with lowest $\mathrm{Im}\,|\tilde{\omega}|$. At extremality, the dominant mode always starts at $\mathrm{Im}\,\tilde{\omega}=0$ and $\mathrm{Re}\,\tilde{\omega}=m\tilde{\Omega}_H^{\hbox{\footnotesize ext}}$ (brown curve). The dark-red point ($a=0=Q$), $\tilde{\omega}\simeq 0.37367168 - 0.08896232\, i $, is the gravitational QNM of Schwarzschild ~[\citenamefont{Chandrasekhar}, 1983, \citenamefont{Leaver}, 1985]. In the right panel, the orange and green regions are so close to the extremal brown curve that they are not visible.}
\label{Fig:Z2l2m2n0}
\end{figure*}

Approximation \eqref{NH:freq} is in excellent agreement with the numerical frequencies (near extremality). This is illustrated in the left and right panels of Fig.~\ref{Fig:spectraFix-a}. For the RN case (left panel), extremality is at $\hat{Q}=1$ and \eqref{NH:freq} with $n=0$ (black line) gives the correct slope for the $\mathrm{NH}_0$ family (green circles), while \eqref{NH:freq} with $n=1$ (magenta line) yields the slope of the $\mathrm{NH}_1$ family (blue squares). On the right panel, we take a KN BH family with $a/a_{\hbox{\footnotesize ext}}=0.96$ (so the whole family of solutions is close to extremality) and compare the numerical results for the dominant $n=0$ QNMs (curve that connects orange diamonds and green circles) with the black  curve, \ie \eqref{NH:freq} with $n=0$.
Moreover, we also compare  \eqref{NH:freq} with $n=1$ (magenta curve) with the $n=1$ numerical modes with the second slowest decay rate (3-branched curve connecting the dark-red triangles, green circles and  blue squares).
So, \eqref{NH:freq} clearly identifies the NH family in the RN limit, and more generically, the dominant modes near extremality.

The right panel of  Fig.~\ref{Fig:spectraFix-a} illustrates a remarkable property of KN QNMs. In the RN case and for small rotation, the  $\mathrm{PS}_0$ family dominates the spectra for  $0 \leq \tilde{Q}<\tilde{Q}_c(\tilde{a})$ (with $\tilde{Q}_c(0)=\tilde{Q}_c^{\hbox{\tiny RN}}$) while the  $\mathrm{NH}_0$ family dominates for $\tilde{Q}_c(\tilde{a})<\tilde{Q}\leq 1$.
But, when  $\tilde{a}$ grows and approaches to extremality, at $a/a_{\hbox{\footnotesize ext}}=0.96$, the $\mathrm{PS}_0$ family {\it merges} with the $\mathrm{NH}_0$ family (orange diamond and green circle curves merge in the right panel of Fig.~\ref{Fig:spectraFix-a}). For higher $a/a_{\hbox{\footnotesize ext}}$ the two families remain merged and this line of solutions approaches $\mathrm{Im} \,\tilde{\omega}=0$, $\mathrm{Re}\, \tilde{\omega}=m \tilde{\Omega}_H^{\hbox{\footnotesize ext}}$ as $a\to a_{\hbox{\footnotesize ext}}$. The whole $n=0$ QNM curve in the right plot is thus well approximated by \eqref{NH:freq}: it captures the $\mathrm{NH}_0$ modes in the RN limit but also the ``$\mathrm{PS}_0$-$\mathrm{NH}_0$ merged" modes (when close to extremality).

The above features of the KN QNMs can be best understood in terms of a critical rotation $\tilde{a}_\star$ (or critical charge $\tilde{Q}_\star=\sqrt{1-\tilde{a}_\star^2}$) in relation to the extremal rotation $\tilde{a}_{\hbox{\footnotesize ext}}$ (or extremal charge $\tilde{Q}_{\hbox{\footnotesize ext}}$).  When $\tilde{a}_\star<\tilde{a}_{\hbox{\footnotesize ext}}\leq 1$ ($0\leq \tilde{Q}_{\hbox{\footnotesize ext}}< \tilde{Q}_\star$), as is the case in the Kerr limit where $\tilde{a}_{\hbox{\footnotesize ext}}=1$,  the PS family terminates at  $\mathrm{Im} \,\tilde{\omega}=0$ and $\mathrm{Re}\, \tilde{\omega}=m \tilde{\Omega}_H^{\hbox{\footnotesize ext}}$ at extremality.  However, when $\tilde{a}_\star> \tilde{a}_{\hbox{\footnotesize ext}}$ ($\tilde{Q}_\star < \tilde{Q}_{\hbox{\footnotesize ext}}$), as is the case in the RN limit where ${\tilde{Q}_{\hbox{\footnotesize ext}}=1}$, the PS family falls short of the ${(\mathrm{Im} \,\tilde{\omega},\mathrm{Re}\, \tilde{\omega})= (0,m \tilde{\Omega}_H^{\hbox{\footnotesize ext}})}$ surface at extremality.

Interestingly, the $\star$ transition point turns out to be given (within numerical error) by the point where the separation constant  $\lambda_2(m,\tilde{a}_{\hbox{\footnotesize ext}})$ in \eqref{NH:freq} vanishes:  $\lambda_2(m,\tilde{a}_\star^{\hbox{\tiny NH}})=0$ ($\lambda_2>0$ for $\tilde{a}_{\hbox{\footnotesize ext}}<\tilde{a}_\star^{\hbox{\tiny NH}}$; $\lambda_2<0$ for $\tilde{a}_{\hbox{\footnotesize ext}}>\tilde{a}_\star^{\hbox{\tiny NH}}$).  To get accurate values for $\tilde{a}_\star^{\hbox{\tiny NH}}$ we use the numerical solution for $\lambda_2$. Alternatively, we  get a good approximation by using the WKB result \eqref{NH:lambda2wkb} for $\lambda_2$:
\be\label{NH:star}
\tilde{a}_\star^{\hbox{\tiny NH}}|_{\hbox{\tiny WKB}}\sim \frac{1}{2}-\frac{5 \sqrt{3} \left(2-\sqrt{2}\right)}{32 \,m}+\frac{5 \left(69-176 \sqrt{2}\right)}{2048 \,m^2}+\mathcal{O}\left(m^{\!-3}\right)
\ee
In the first case we get $\{\tilde{a}_\star,\tilde{Q}_\star\}^{\hbox{\tiny NH}}\simeq \{0.360, 0.932\}$ while \eqref{NH:star} yields $\{\tilde{a}_\star,\tilde{Q}_\star\}^{\hbox{\tiny NH}}_{\hbox{\tiny WKB}}\sim\{0.311, 0.970\}$ (for $m=2$) \footnote{The eikonal analysis \eqref{PS:eikonal} also predicts the $\star$ transition point. Namely, in the $m\to\infty$ limit it predicts $\tilde{a}_\star^{\hbox{\tiny eikn}}=1/2$ which is, as expected, not a good approximation to $\tilde{a}_\star\simeq 0.360$. However, in the Supplemental Material, we show that the curve $\tilde{a}_\star(m)$  increasingly agrees with the  eikonal PS prediction \eqref{PS:eikonal} when $m$ grows.}.

In summary, our  analysis uncovers a surprising property not observed in the QNM spectra of Schwarzschild, Kerr or RN. Indeed, in the KN QNM spectra we observe a phenomenon know as {\it eigenvalue repulsion} \footnote{It could well be that eigenvalue repulsion is also ultimately responsible for the special features displayed by 1) the $n=5$ (\ie $n=6$ if we start counting them at $n=1$) overtone of the $\ell=m=2$ photon sphere QNM of Kerr (see Fig.~4 of [\citenamefont{Onozawa}, 1997] and [\citenamefont{Berti et~al.}, 2009]), and  2) by the QNM  spectra of de Sitter RN black holes [\citenamefont{Dias and Santos}, 2020].}. The latter is common in solid state physics when \eg electrons move in certain Schr\"odinger potentials that introduce energy bands/gaps (see \eg section 7 of~[\citenamefont{Kittel}, 2004]). The eigenvalue repulsion feature is most evident by considering the evolution of the 3 plots in  Fig.~\ref{Fig:spectraFix-a}. In the RN case (left plot), and for small rotation, we have a sharp and unambiguous distinction between the four families of modes represented. In particular,  the $\mathrm{PS}_0$ family dominates the spectra for  $0 \leq \hat{Q}<\hat{Q}_c(\hat{a})$ (with $\hat{Q}_c(0)=\hat{Q}_c^{\hbox{\tiny RN}}$) while the $\mathrm{NH}_0$ family dominates for $\hat{Q}_c(\hat{a})<\hat{Q}\leq 1$. The two modes intersect at $\hat{Q}=\hat{Q}_c(\hat{a})$ with a simple crossover and similar crossovers occur when the $\mathrm{PS}_1$ curve intersects the $\mathrm{NH}_0$ or $\mathrm{NH}_1$ curves. However, at  $a/a_{\hbox{\footnotesize ext}}=0.39$ (middle panel), we find that eigenvalue repulsion occurs between the $\mathrm{PS}_1$ and $\mathrm{NH}_0$ families: the $\mathrm{PS}_1$ curve breaks into two pieces and the same occurs for the $\mathrm{NH}_0$ curve. The left (right) branch of the $\mathrm{PS}_1$  family now connects to the right (left) branch of the $\mathrm{NH}_0$ curve and a {\it frequency gap} appears between the two new curves in the neighbourhood of the two associated kinks. The distinction between the families is no longer sharp. As the rotation increases, new eigenvalue repulsions occur. For example, at $a/a_{\hbox{\footnotesize ext}}=0.96$, the $\mathrm{PS}_0$ curve breaks into two pieces and the same occurs (again) for the $\mathrm{NH}_0$ curve. The left branch of the $\mathrm{PS}_0$ family now merges with the right branch of the $\mathrm{NH}_0$ curve and this new curve is well described by the black curve \eqref{NH:freq} (not shown: the right branch of the  $\mathrm{PS}_0$ curve merges with a $n>1$ NH curve). Below, the left branch of the $\mathrm{NH}_0$ curve now bridges the dark-red triangle $\mathrm{PS}_1$ curve with the blue square $\mathrm{NH}_1$ curve (the $\mathrm{NH}_1$ curve also breaks and merges with another $n>1$ curve but we do not show these further sub-dominant modes).

\emph{\bf Full QNM spectra.}
The full spectra of the most dominant KN QNMs  $-$ classified as $Z_2$, $\ell=m=2$, $n=0$ by~[\citenamefont{Chandrasekhar}, 1983] (Table V, page 262) in the Schwarzschild limit $-$ is given in Fig.~\ref{Fig:Z2l2m2n0}. The left/right panel gives the imaginary/real part of the frequency.
The brown curve has $\mathrm{Im}\,\tilde{\omega}=0$, $\mathrm{Re}\,\tilde{\omega}=m\tilde{\Omega}_H^{\hbox{\footnotesize ext}}$.
To scan the 2-dimensional parameter space we used a grid with $100\times 100$ points in $[0,1]\times[0,1]$ for $\{\hat{Q}, a/a_{\hbox{\footnotesize ext}}\}$ with $\hat{a}_{\hbox{\footnotesize ext}} = \sqrt{1-\hat{Q}^2}$.

The KN modes with slowest decay rate always terminate at extremality along the extremal brown curve, with the frequencies off-extremality well approximated by \eqref{NH:freq} as illustrated in Fig.~\ref{Fig:spectraFix-a}.
The red surface family, continuously connected to the Schwarzschild mode (dark-red point ~[\citenamefont{Chandrasekhar}, 1983, \citenamefont{Leaver}, 1985]), is the $\mathrm{PS}_0$ QNM family as we unambiguously identify it in the RN limit. It dominates the spectra for most of the parameter space. However, for large $\tilde{Q}$ it is instead  the $\mathrm{NH}_0$ QNM family (green surface) that has the  lowest $|\mathrm{Im}\,\tilde{\omega}|$. In between these orange/green regions there is a yellowish zone. This is where either simple crossovers  (that trade mode dominance) or eigenvalue repulsions between the $\mathrm{PS}_0$ and $\mathrm{NH}_0$ modes occurs. These were already analysed in the discussion of Fig.~\ref{Fig:spectraFix-a}.
The derived QNM spectra can be used to model beyond Standard Model physics in binary mergers and GW emission in realistic astrophysical environments, bearing increasing importance with future enhancements in sensitivity of current and planned GW observatories.
In a companion paper [\citenamefont{Carullo et~al.}, 2021], we apply the results obtained in this work to the latest observations from the GW detector network.

\smallskip

\noindent{\bf Acknowledgments.}

The authors would like to thank Nathan Johnson-McDaniel for helpful discussions.
We acknowledge the use of the cluster `Baltasar-Sete-S\'ois', and associated support services at CENTRA/IST, in the completion of this work. The authors further acknowledge the use of the IRIDIS High Performance Computing Facility, and associated support services at the University of Southampton, in the completion of this work.
O.~C.~D. acknowledges financial support from the STFC ``Particle Physics Grants Panel (PPGP) 2016" Grant No.~ST/P000711/1 and the STFC ``Particle Physics Grants Panel (PPGP) 2018" Grant No.~ST/T000775/1. M.~G is supported by a Royal Society University Research Fellowship. J.~E.~S. has been partially supported by STFC consolidated grants ST/P000681/1, ST/T000694/1. The research leading to these results has received funding from the European Research Council under the European Community's Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement no. [247252].

\newpage
%%% BEGINNING OF APPENDIX %%%
\begin{appendix}
\onecolumngrid
\section{\Large Supplemental Material}\label{sec:Appendix}

\subsection{Coupled pair of PDEs for the KN perturbations}\label{sec:Appendix1}

The uniqueness theorems [51, \citenamefont{Chrusciel et~al.}, 2012] state that the Kerr-Newman (KN) black hole (BH) is the unique, most general family of stationary asymptotically flat BHs, of Einstein-Maxwell theory. It is characterised by 3 parameters: mass $M$, angular momentum $J\equiv M a$ and charge $Q$. The Kerr, Reissner-Nordstr\"om (RN) and Schwarzschild (Schw) BHs constitute limiting cases: ${Q=0}$, $a=0$ and $Q=a=0$, respectively.
The gravitational and Maxwell fields of the KN BH in  Boyer-Lindquist coordinates are given by [\citenamefont{Newman et~al.}, 1965, \citenamefont{Adamo and Newman}, 2014]
\begin{eqnarray}\label{KNsoln}
ds^2&=&-\frac{\Delta}{\Sigma} \left(\dd t-a \sin^2\theta \dd \phi  \right)^2+\frac{\Sigma }{\Delta }\,\dd r^2 + \Sigma \,\dd \theta^2
+ \frac{\sin ^2\theta}{\Sigma }\left[\left(r^2+a^2\right)\dd \phi -a \dd t \right]^2, \nonumber\\
A&=& \frac{Q \,r}{\Sigma}\left(\dd t-a \sin^2\theta \dd \phi \right),
\end{eqnarray}
with $\Delta = r^2 -2Mr+a^2+Q^2$ and $\Sigma=r^2+a^2 \cos^2\theta$.

Linear gravito-electromagnetic perturbations about the KN background are more easily addressed in the  Newman-Penrose (NP) formalism [\citenamefont{Newman and Penrose}, 1962].
In the context of this formalism there is a well-known set of NP scalars built of contractions of the NP tetrad with the Weyl tensor (\eg $\Psi_2$, $\Psi_3$ and $\Psi_4$) or with the Maxwell field strength (\eg $\Phi_1$ and $\Phi_2$) [\citenamefont{Chandrasekhar}, 1983, \citenamefont{Stephani et~al.}, 2003] . Out of these, one can construct two
{\it gauge invariant} perturbed quantities, \ie quantities that are invariant under both linear diffeomorphisms and tetrad rotations, namely  [\citenamefont{Dias et~al.}, 2015]:
\begin{eqnarray}\label{gauging}
&&\psi_{-2}= \left(\bar{r}^*\right)^4 \Psi_4^{(1)},  \nonumber\\
&& \psi_{-1}=\frac{\left(\bar{r}^*\right)^3}{2\sqrt{2}\Phi_1^{(0)}} \left(2\Phi_1^{(0)}\Psi_3^{(1)} -3 \Psi_2^{(0)}\Phi_2^{(1)}\right),
\end{eqnarray}
with $\bar{r} = r+ia\cos \theta$. Here, NP scalars with superscript $^{(0)}$ refer to scalars in the KN background and the superscript $^{(1)}$ to first order perturbations of the scalar.
These  NP scalars \eqref{gauging} are the ones relevant for the study of perturbations that are outgoing at future null infinity and regular at the future horizon \footnote{There is a set of two coupled PDEs---related to (4) by a Geroch-Held-Penrose [\citenamefont{Geroch et~al.}, 1973] transformation---for the quantities $\psi_{2}$ and $\psi_{1}$ that are the positive spin counterparts of (4); however these would be relevant if we were interested in perturbations that were outgoing at past null infinity.}.
Ref. [\citenamefont{Dias et~al.}, 2015] derived a set of two coupled partial differential equations (PDEs) for $\psi_{-2}$ and $\psi_{-1}$ that describe the most general perturbations (except for trivial modes that shift the parameters of the solution) of a KN BH, namely:
\begin{eqnarray}\label{ChandraEqsAppendix}
&& \left(\mathcal{F}_{-2}+ Q^2 \mathcal{G}_{-2}\right) \psi_{-2}  + Q^2 \mathcal{H}_{-2}  \psi_{-1} =0 \,, \nonumber \\
&& \left(\mathcal{F}_{-1} +Q^2 \mathcal{G}_{-1}\right)\psi_{-1} + Q^2  \mathcal{H}_{-1} \psi_{-2}=0  \,,
\end{eqnarray}
where the second order differential operators $\{\mathcal{F},\mathcal{G},\mathcal{H}\}$ are given by  [\citenamefont{Dias et~al.}, 2015]
\begin{eqnarray}\label{def:opsFGH}
\mathcal{F}_{-2}&=&\Delta\DD_{-1}^\dagger\DD_0 +\LL_{-1}\LL_2^\dagger -6i \omega\bar{r} \,,
\nonumber \\
\mathcal{G}_{-2}&=&\Delta \DD_{-1}^\dagger \alpha_-\bar{r}^*\DD_0  -3\Delta \DD_{-1}^\dagger \alpha_-
- \LL_{-1}\alpha_+ \bar{r}^* \LL_2 ^\dagger  +3 \LL_{-1} \alpha_+ i a \sin \theta \,,
\nonumber \\
\mathcal{H}_{-2}&=&-\Delta \DD_{-1}^\dagger \alpha_- \bar{r}^* \LL_{-1}  -3 \Delta \DD_{-1}^\dagger \alpha_- i a \sin \theta
-\LL_{-1} \alpha_+ \bar{r}^* \Delta \DD_{-1}^\dagger  -3\LL_{-1} \alpha_+ \Delta  \,,
\nonumber \\
\mathcal{F}_{-1}&=&\Delta\DD_1\DD_{-1}^\dagger +\LL_2^\dagger\LL_{-1}-6i \omega\bar{r} \,,
\\
\mathcal{G}_{-1}&=& - \DD_0 \alpha_+ \bar{r}^* \Delta \DD_{-1}^\dagger  -3 \DD_0 \alpha_+ \Delta
+\LL_2^\dagger \alpha_- \bar{r}^* \LL_{-1}  +3 \LL_2^\dagger \alpha_- i a\sin\theta \,,
\nonumber \\
\mathcal{H}_{-1}&=& -\DD_0 \alpha_+ \bar{r}^* \LL_2^\dagger  +3 \DD_0 \alpha_+ i a \sin \theta
-\LL_2^\dagger \alpha_- \bar{r}^* \DD_0  +3 \LL_2^\dagger \alpha _- \,,
\nonumber
\end{eqnarray}
with %$\bar{r}\equiv  r+ia\cos\theta$,
$\alpha_\pm \equiv \left[3(\bar{r}^2M-\bar{r} Q^2)\pm Q^2\bar{r}^*\right]^{-1}$,  and we introduced the radial and angular Chandrasekhar operators  [\citenamefont{Chandrasekhar}, 1983],
\begin{eqnarray}\label{def:DL}
&& \DD_j = \partial_r+\frac{i K_r}{\Delta}+2j\frac{(r-M)}{\Delta}, \quad K_r=am-(r^2+a^2)\omega; \nonumber \\
&& \LL_j = \partial_\theta+K_{\theta}+j\cot\theta, \quad K_{\theta}=\frac{m}{\sin\theta}-a\omega\sin\theta.
\end{eqnarray}
The complex conjugate of these operators, namely $\DD_j^\dagger $ and $\LL_j^\dagger$, can be obtained from $\DD_j$ and $\LL_j$ via the replacement $K_r \to - K_r$ and $K_{\theta} \to - K_{\theta}$, respectively.

Note that fixing a gauge in which $\Phi_{0}^{(1)}=\Phi_{1}^{(1)}=0$, \eqref{ChandraEqsAppendix} reduces to the Chandrasekhar coupled PDE system [\citenamefont{Chandrasekhar}, 1983] (see also the derivation in [\citenamefont{Mark et~al.}, 2014]).  Finally, note that in the limit $Q\to 0$ \eqref{ChandraEqsAppendix}  decouple yielding the familiar Teukolsky equation for Kerr  [\citenamefont{Teukolsky}, 1972].

Since $\partial_t,\partial_\phi$ are Killing vector fields of KN, we can Fourier decompose the perturbations $\{\psi_{-2},\psi_{-1}\}$ as $e^{-i \omega t} e^{i m \phi}$. This introduces the frequency $\omega$ and azimuthal quantum number $m$ of the perturbation. The $t -\phi$ symmetry of the KN BH allows to consider only modes with  Re$(\omega)\geq 0$, as long as we study both signs of $m$.
Then, to solve the coupled PDEs \eqref{gauging}, we need to impose physical boundary conditions (BCs).
At spatial infinity, a Frobenius analysis of \eqref{ChandraEqsAppendix} that allows only outgoing waves yields the decay:
\begin{equation}\label{BC:inf}
\psi_{s}{\bigl |}_\infty \!\simeq\!e^{i \omega r} r^{-(2s+1)+i \omega \,\frac{r_+^2+a^2+Q^2}{r_+}} \!\! \left( \!\! \alpha_{s}(\theta)+\frac{\beta_{s}(\theta)}{r}+\cdots\!\!\right), \nonumber
\end{equation}
where $s=-2,-1$, and $\beta_{s}(\theta)$ is a function of $\alpha_{s}(\theta)$ and its derivative fixed by expanding \eqref{ChandraEqsAppendix} at spatial infinity.

At the horizon, a Frobenius analysis whereby we require only regular modes in ingoing Eddington-Finkelstein coordinates, yields the expansion
\begin{equation}\label{BC:H}
\psi_{s}{\bigl |}_H \!\simeq\! \left(r-r_+\right)^{-s-\frac{i (\omega -m\Omega_H)}{4 \pi T_H}}[ a_{s}(\theta)+ b_{s}(\theta)(r-r_+) +\cdots ], \nonumber
\end{equation}
where $b_{s}(\theta)$ is a function of $a_s(\theta)$ and its derivative.

At the North (South) pole $x\equiv \cos\theta =1\,(-1)$, regularity dictates that the fields must behave as
($\varepsilon = 1$ for $|m|\geq 2$, while $\varepsilon = -1$ for $|m|=0,1$ modes)
\begin{equation}\label{BC:N}
\psi_{s}{\bigl |}_{\hbox{\tiny N,(S)}} \hspace{-1pt} \simeq  (1\mp x)^{\varepsilon^{\frac{1\pm 1}{2}} \frac{s+|m|}{2}} \hspace{-1pt} \left[ A^{\pm}_{s}(r)+B^{\pm}_{s}(r)(1\mp x)+\cdots \right],  \nonumber
\end{equation}
where $B^{+}_{s}(r)$($B^{-}_{s}(r)$) is a function of $A^{+}_{s}(r)$($A^{-}_{s}(r)$) and its derivatives along $r$, whose exact form is fixed by expanding \eqref{ChandraEqsAppendix} around the North (South) pole.

\subsection{WKB coefficients for the separation constant $\lambda_2$}\label{sec:NHappendix}

At extremality, the modes with slowest decay rate (independently of belonging to the NH or PS families) always approach $\mathrm{Im}\,\tilde{\omega}=0$ and $\mathrm{Re}\,\tilde{\omega}=m \tilde{\Omega}_H^{\hbox{\footnotesize{ext}}}$ and \eqref{NH:freq} of the main text provides an excellent approximation to their frequency in an expansion off-extremality (as analysed in the discussion of Fig.~\ref{Fig:spectraFix-a} of the main text). The derivation of the analytical approximation \eqref{NH:freq} of the main text is quite long and thus we will present it in the companion manuscript [46].

In \eqref{NH:freq} of the main text, the separation constant $\lambda_2$ has a WKB expansion for large $m$, as given in Eq. \eqref{NH:lambda2wkb} of the main text. The associated WKB coefficients
\begin{subequations}\label{NH:WKBansatzCoef}
\begin{align}
&\lambda_{2,0}=4 \left(1-4 \hat{a} ^2\right),\qquad
\lambda_{2,1}= -4 \left(1+\hat{a}^2\right) \left(2 \sqrt{1-\hat{a} ^2}-\sqrt{1+2 \hat{a} ^2}\right),
\\
&\lambda_{2,2}= \frac{3 \sqrt{1-\hat{a} ^2} \left(1+\hat{a}^2\right)^2 \left(3-726 \hat{a} ^{10}-253 \hat{a} ^8+128 \hat{a} ^6-74 \hat{a} ^4-50 \hat{a} ^2\right)}{\left(1+2\hat{a}^2\right) \left[\left(66 \hat{a} ^6-5 \hat{a} ^4-12 \hat{a} ^2+5\right) \sqrt{1-\hat{a} ^2}+4 \left(1-\hat{a} ^4\right) \sqrt{2 \hat{a} ^2+1}\right]},
\tag{\stepcounter{equation}\theequation}   \\
\bigg[
4 \left(1+2\hat{a}^2\right)^{7/2}\bigg(
578577650112 \hat{a} ^{40}-338129795520 \hat{a} ^{38}-1042453021104 \hat{a} ^{36}+1170932108544 \hat{a} ^{34}
\nonumber \\
&\hspace{0.8cm} +243872180244 \hat{a} ^{32}-1092788709804 \hat{a} ^{30}+457571937931 \hat{a} ^{28}+286639850738 \hat{a} ^{26}-371225227587 \hat{a} ^{24}
\nonumber \\
+75821376048 \hat{a} ^{22}+83823143199 \hat{a} ^{20}-64522516578 \hat{a} ^{18}+5397537793 \hat{a} ^{16}+11870759300 \hat{a} ^{14}-5939331087 \hat{a} ^{12}
\nonumber \\
+15670254 \hat{a} ^{10}+798959271 \hat{a} ^8-269248008 \hat{a} ^6-8868395 \hat{a} ^4+20327618 \hat{a} ^2-4782969
\bigg)
\nonumber \\
+4 \sqrt{1-\hat{a} ^2} \left(1+2\hat{a}^2\right)^3\bigg(
661231600128 \hat{a} ^{40}-788969522880 \hat{a} ^{38}-475886378880 \hat{a} ^{36}+1029138506352 \hat{a} ^{34}
\nonumber \\
-630648141552 \hat{a} ^{32}-452699156052 \hat{a} ^{30}+658166339168 \hat{a} ^{28}-186975958943 \hat{a} ^{26}-249892000005 \hat{a} ^{24}
\nonumber \\
+178743692406 \hat{a} ^{22}-3249242106 \hat{a} ^{20}-56479482309 \hat{a} ^{18}+20902690721 \hat{a} ^{16}+3663601312 \hat{a} ^{14}-5845481340 \hat{a} ^{12}
\nonumber \\
+1100552199 \hat{a} ^{10}+410656173 \hat{a} ^8-279409506 \hat{a} ^6+19829366 \hat{a} ^4+13153165 \hat{a} ^2-4782969
\bigg)\bigg]^{-1}
\nonumber \\
\bigg[
3 \hat{a} ^2 \sqrt{1-\hat{a} ^2} \left(1+\hat{a}^2\right)^3 \sqrt{2 \hat{a} ^2+1} \bigg(
90588729217536 \hat{a} ^{46}+93586813404480 \hat{a} ^{44}-64234642488192 \hat{a} ^{42}
\nonumber \\
-54181551934224 \hat{a} ^{40}+14733709326864 \hat{a} ^{38}-34708141099764 \hat{a} ^{36}-8979094220672 \hat{a} ^{34}+34432474064505 \hat{a} ^{32}
\nonumber \\
-10922161747605 \hat{a} ^{30}-23041644949212 \hat{a} ^{28}+5136927583340 \hat{a} ^{26}+4733507876355 \hat{a} ^{24}-3578226571619 \hat{a} ^{22}
\nonumber \\
-898929274206 \hat{a} ^{20}+753565243446 \hat{a} ^{18}-135077374365 \hat{a} ^{16}-174223122235 \hat{a} ^{14}+33089919120 \hat{a} ^{12}
\nonumber \\
+8380363168 \hat{a} ^{10}-9890782275 \hat{a} ^8-803782461 \hat{a} ^6+541670718 \hat{a} ^4-148272034 \hat{a} ^2-57395628  \bigg)
\nonumber \\
+3 \hat{a} ^2 \left(1+\hat{a}^2\right)^3 \bigg(
158530276130688 \hat{a} ^{48}+192260601732672 \hat{a} ^{46}-226279077675552 \hat{a} ^{44}
\nonumber \\
-257580189150768 \hat{a} ^{42}+238634465705064 \hat{a} ^{40}+187478664334236 \hat{a} ^{38}-167948153974214 \hat{a} ^{36}
\nonumber \\
-79050787933609 \hat{a} ^{34}+69165996968940 \hat{a} ^{32}+1562277529575 \hat{a} ^{30}-26149776558142 \hat{a} ^{28}
\nonumber \\
+6310859786413 \hat{a} ^{26}+3820171951948 \hat{a} ^{24}-4424582883901 \hat{a} ^{22}-417658252182 \hat{a} ^{20}+868831525263 \hat{a} ^{18}
\nonumber \\
-249677209480 \hat{a} ^{16}-170706582299 \hat{a} ^{14}+47404470046 \hat{a} ^{12}+4708012127 \hat{a} ^{10}-10932078636 \hat{a} ^8-398469675 \hat{a} ^6
\nonumber \\
+532105820 \hat{a} ^4-176969858 \hat{a} ^2-57395628
\bigg)\bigg].
\end{align}
\end{subequations}
The derivation of \eqref{NH:lambda2wkb} of the main text and of \eqref{NH:WKBansatzCoef} is again  long and will be given it in the companion manuscript [46]. There, we also show that this WKB expansion provides an excellent approximation already for $m=10$ and a good approximation even for $m=2$.

\end{appendix}

\begin{thebibliography}{62}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname bibnamefont\endcsname\relax
\def\bibnamefont#1{#1}\fi
\expandafter\ifx\csname bibfnamefont\endcsname\relax
\def\bibfnamefont#1{#1}\fi
\expandafter\ifx\csname citenamefont\endcsname\relax
\def\citenamefont#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
\def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi
\providecommand{\bibinfo}[2]{#2}
\providecommand{\eprint}[2][]{\url{#2}}

\bibitem[{[\citenamefont{Mazur}, 2000](2000)}]{Mazur}
\bibinfo{author}{\bibfnamefont{P.~O.} \bibnamefont{Mazur}}
(\bibinfo{year}{2000}), \eprint{hep-th/0101012}.

\bibitem[{[\citenamefont{Gibbons}, 1975](1975)}]{Gibbons}
\bibinfo{author}{\bibfnamefont{G.~W.} \bibnamefont{Gibbons}},
\bibinfo{journal}{Communications in Mathematical Physics}
\textbf{\bibinfo{volume}{44}}, \bibinfo{pages}{245 } (\bibinfo{year}{1975}),
\urlprefix\url{https://doi.org/}.

[\citenamefont{Blandford and Znajek}, 1977]
\bibinfo{author}{\bibfnamefont{R.~D.} \bibnamefont{Blandford}}
\bibnamefont{and} \bibinfo{author}{\bibfnamefont{R.~L.}
\bibnamefont{Znajek}}, \bibinfo{journal}{Monthly Notices of the Royal
Astronomical Society} \textbf{\bibinfo{volume}{179}}, \bibinfo{pages}{433}
(\bibinfo{year}{1977}), ISSN \bibinfo{issn}{0035-8711},
\eprint{https://academic.oup.com/mnras/article-pdf/179/3/433/9333653/mnras179-0433.pdf},
\urlprefix\url{https://doi.org/10.1093/mnras/179.3.433}.

[\citenamefont{Aasi et~al.}, 2015]
\bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Aasi}} \bibnamefont{et~al.}
(\bibinfo{collaboration}{LIGO Scientific}), \bibinfo{journal}{Class. Quant.
Grav.} \textbf{\bibinfo{volume}{32}}, \bibinfo{pages}{074001}
(\bibinfo{year}{2015}), \eprint{1411.4547}.

[\citenamefont{Acernese et~al.}, 2015]
\bibinfo{author}{\bibfnamefont{F.}~\bibnamefont{Acernese}} \bibnamefont{et~al.}
(\bibinfo{collaboration}{VIRGO}), \bibinfo{journal}{Class. Quant. Grav.}
\textbf{\bibinfo{volume}{32}}, \bibinfo{pages}{024001}
(\bibinfo{year}{2015}), \eprint{1408.3978}.

[\citenamefont{Abbott et~al.}, 2020]
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Abbott}} \bibnamefont{et~al.}
(\bibinfo{collaboration}{LIGO Scientific, Virgo})
(\bibinfo{year}{2020}{\natexlab{a}}), \eprint{2010.14527}.

[\citenamefont{Gupta et~al.}, 2021]
\bibinfo{author}{\bibfnamefont{P.~K.} \bibnamefont{Gupta}},
\bibinfo{author}{\bibfnamefont{T.~F.~M.} \bibnamefont{Spieksma}},
\bibinfo{author}{\bibfnamefont{P.~T.~H.} \bibnamefont{Pang}},
\bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Koekoek}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{C.~V.~D.} \bibnamefont{Broeck}}
(\bibinfo{year}{2021}), \eprint{2107.12111}.

[\citenamefont{Bozzola and Paschalidis}, 2020]
\bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Bozzola}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{Paschalidis}}
(\bibinfo{year}{2020}), \eprint{2006.15764}.

[\citenamefont{Abbott et~al.}, 2020]
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Abbott}} \bibnamefont{et~al.}
(\bibinfo{collaboration}{LIGO Scientific, Virgo})
(\bibinfo{year}{2020}{\natexlab{b}}), \eprint{2010.14529}.

[\citenamefont{Dias et~al.}, 2015]
\bibinfo{author}{\bibfnamefont{O.~J.~C.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Godazgar}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{114}},
\bibinfo{pages}{151101} (\bibinfo{year}{2015}), \eprint{1501.04625}.

[\citenamefont{Chandrasekhar}, 1983]
\bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Chandrasekhar}},
\emph{\bibinfo{title}{The Mathematical Theory of Black Holes}}
(\bibinfo{publisher}{Oxford Press (1983)}, \bibinfo{year}{1983}).

[\citenamefont{Mark et~al.}, 2014]
\bibinfo{author}{\bibfnamefont{Z.}~\bibnamefont{Mark}},
\bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Yang}},
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Zimmerman}},
\bibnamefont{and} \bibinfo{author}{\bibfnamefont{Y.}~\bibnamefont{Chen}}
(\bibinfo{year}{2014}), \eprint{1409.5800}.

[\citenamefont{Pani et~al.}, 2013]
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Pani}},
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Berti}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{L.}~\bibnamefont{Gualtieri}},
\bibinfo{journal}{Phys.Rev.Lett.} \textbf{\bibinfo{volume}{110}},
\bibinfo{pages}{241103} (\bibinfo{year}{2013}{\natexlab{a}}),
\eprint{1304.1160}.

[\citenamefont{Pani et~al.}, 2013]
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Pani}},
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Berti}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{L.}~\bibnamefont{Gualtieri}},
\bibinfo{journal}{Phys.Rev.} \textbf{\bibinfo{volume}{D88}},
\bibinfo{pages}{064048} (\bibinfo{year}{2013}{\natexlab{b}}),
\eprint{1307.7315}.

[\citenamefont{Zilh\~ao et~al.}, 2014]
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Zilh\~ao}},
\bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{Cardoso}},
\bibinfo{author}{\bibfnamefont{C.}~\bibnamefont{Herdeiro}},
\bibinfo{author}{\bibfnamefont{L.}~\bibnamefont{Lehner}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{U.}~\bibnamefont{Sperhake}},
\bibinfo{journal}{Phys.Rev.} \textbf{\bibinfo{volume}{D90}},
\bibinfo{pages}{124088} (\bibinfo{year}{2014}), \eprint{1410.0694}.

[\citenamefont{Akutsu et~al.}, 2020]
\bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Akutsu}} \bibnamefont{et~al.}
(\bibinfo{collaboration}{KAGRA}) (\bibinfo{year}{2020}), \eprint{2005.05574}.

[\citenamefont{Punturo et~al.}, 2010]
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Punturo}},
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Abernathy}},
\bibinfo{author}{\bibfnamefont{F.}~\bibnamefont{Acernese}},
\bibinfo{author}{\bibfnamefont{B.}~\bibnamefont{Allen}},
\bibinfo{author}{\bibfnamefont{N.}~\bibnamefont{Andersson}},
\bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Arun}},
\bibinfo{author}{\bibfnamefont{F.}~\bibnamefont{Barone}},
\bibinfo{author}{\bibfnamefont{B.}~\bibnamefont{Barr}},
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Barsuglia}},
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Beker}},
\bibnamefont{et~al.}, \bibinfo{journal}{Classical and Quantum Gravity}
\textbf{\bibinfo{volume}{27}}, \bibinfo{pages}{194002}
\urlprefix\url{https://doi.org/10.1088%2F0264-9381%2F27%2F19%2F194002}.

[\citenamefont{Reitze et~al.}, 2019]
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Reitze}} \bibnamefont{et~al.},
\bibinfo{journal}{Bull. Am. Astron. Soc.} \textbf{\bibinfo{volume}{51}},
\bibinfo{pages}{035} (\bibinfo{year}{2019}), \eprint{1907.04833}.

[\citenamefont{Amaro-Seoane et~al.}, 2017]
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Amaro-Seoane}},
\bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Audley}},
\bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Babak}},
\bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Baker}},
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Barausse}},
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Bender}},
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Berti}},
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Binetruy}},
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Born}},
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Bortoluzzi}},
\bibnamefont{et~al.}, \emph{\bibinfo{title}{Laser interferometer space
antenna}} (\bibinfo{year}{2017}), \eprint{1702.00786}.

[\citenamefont{{Cardoso} et~al.}, 2016]
\bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{{Cardoso}}},
\bibinfo{author}{\bibfnamefont{C.~F.~B.} \bibnamefont{{Macedo}}},
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{{Pani}}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{{Ferrari}}},
\bibinfo{journal}{jcap} \textbf{\bibinfo{volume}{2016}}, \bibinfo{eid}{054}
(\bibinfo{year}{2016}), \eprint{1604.07845}.

[\citenamefont{Carullo et~al.}, 2021]
\bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Carullo}},
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Laghi}},
\bibinfo{author}{\bibfnamefont{N.~K.} \bibnamefont{Johnson-McDaniel}},
\bibinfo{author}{\bibfnamefont{W.}~\bibnamefont{Del~Pozzo}},
\bibinfo{author}{\bibfnamefont{O.~J.~C.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Godazgar}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibinfo{journal}{Submitted to Phys. Rev. D.}  (\bibinfo{year}{2021}).

[\citenamefont{Adamo and Newman}, 2014]
\bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Adamo}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Newman}},
\textbf{\bibinfo{volume}{31791}}, \bibinfo{pages}{2014}
(\bibinfo{year}{2014}), \eprint{1410.6626}.

[\citenamefont{Dias et~al.}, 2016]
\bibinfo{author}{\bibfnamefont{O.~J.~C.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibnamefont{and} \bibinfo{author}{\bibfnamefont{B.}~\bibnamefont{Way}},
\bibinfo{journal}{Class. Quant. Grav.} \textbf{\bibinfo{volume}{33}},
\bibinfo{pages}{133001} (\bibinfo{year}{2016}), \eprint{1510.02804}.

[\citenamefont{Dias et~al.}, 2009]
\bibinfo{author}{\bibfnamefont{O.~J.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Figueras}},
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Monteiro}},
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibnamefont{and} \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Emparan}},
\bibinfo{journal}{Phys.Rev.} \textbf{\bibinfo{volume}{D80}},
\bibinfo{pages}{111701} (\bibinfo{year}{2009}), \eprint{0907.2248}.

[\citenamefont{Dias et~al.}, 2010]
\bibinfo{author}{\bibfnamefont{O.~J.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Figueras}},
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Monteiro}},
\bibinfo{author}{\bibfnamefont{H.~S.} \bibnamefont{Reall}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibinfo{journal}{JHEP} \textbf{\bibinfo{volume}{1005}}, \bibinfo{pages}{076}
(\bibinfo{year}{2010}{\natexlab{a}}), \eprint{1001.4527}.

[\citenamefont{Dias et~al.}, 2010]
\bibinfo{author}{\bibfnamefont{O.~J.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Figueras}},
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Monteiro}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibinfo{journal}{Phys.Rev.} \textbf{\bibinfo{volume}{D82}},
\bibinfo{pages}{104025} (\bibinfo{year}{2010}{\natexlab{b}}),
\eprint{1006.1904}.

[\citenamefont{Dias et~al.}, 2010]
\bibinfo{author}{\bibfnamefont{O.~J.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Figueras}},
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Monteiro}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibinfo{journal}{JHEP} \textbf{\bibinfo{volume}{1012}}, \bibinfo{pages}{067}
(\bibinfo{year}{2010}{\natexlab{c}}), \eprint{1011.0996}.

[\citenamefont{Dias et~al.}, 2011]
\bibinfo{author}{\bibfnamefont{O.~J.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Monteiro}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibinfo{journal}{JHEP} \textbf{\bibinfo{volume}{1108}}, \bibinfo{pages}{139}
(\bibinfo{year}{2011}), \eprint{1106.4554}.

[\citenamefont{Dias et~al.}, 2010]
\bibinfo{author}{\bibfnamefont{O.~J.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Monteiro}},
\bibinfo{author}{\bibfnamefont{H.~S.} \bibnamefont{Reall}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibinfo{journal}{JHEP} \textbf{\bibinfo{volume}{1011}}, \bibinfo{pages}{036}
(\bibinfo{year}{2010}{\natexlab{d}}), \eprint{1007.3745}.

[\citenamefont{Dias et~al.}, 2012]
\bibinfo{author}{\bibfnamefont{O.~J.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Figueras}},
\bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Minwalla}},
\bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Mitra}},
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Monteiro}},
\bibnamefont{et~al.}, \bibinfo{journal}{JHEP}
\textbf{\bibinfo{volume}{1208}}, \bibinfo{pages}{117} (\bibinfo{year}{2012}),
\eprint{1112.4447}.

[\citenamefont{Cardoso et~al.}, 2014]
\bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{Cardoso}},
\bibinfo{author}{\bibfnamefont{O.~J.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{G.~S.} \bibnamefont{Hartnett}},
\bibinfo{author}{\bibfnamefont{L.}~\bibnamefont{Lehner}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibinfo{journal}{JHEP} \textbf{\bibinfo{volume}{1404}}, \bibinfo{pages}{183}
(\bibinfo{year}{2014}), \eprint{1312.5323}.

[\citenamefont{Dias et~al.}, 2014]
\bibinfo{author}{\bibfnamefont{O.~J.~C.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{G.~S.} \bibnamefont{Hartnett}},
\bibnamefont{and} \bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}}
(\bibinfo{year}{2014}), \eprint{1402.7047}.

[\citenamefont{Dias et~al.}, 2018]
\bibinfo{author}{\bibfnamefont{O.~J.~C.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{H.~S.} \bibnamefont{Reall}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}}
(\bibinfo{year}{2018}), \eprint{1808.02895}.

[\citenamefont{Leaver}, 1985]
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Leaver}},
\bibinfo{journal}{Proc.Roy.Soc.Lond.} \textbf{\bibinfo{volume}{A402}},
\bibinfo{pages}{285} (\bibinfo{year}{1985}).

[\citenamefont{{Goebel}}, 1972]
\bibinfo{author}{\bibfnamefont{C.~J.} \bibnamefont{{Goebel}}},
\bibinfo{journal}{Astrophys. J.} \textbf{\bibinfo{volume}{172}},
\bibinfo{pages}{L95} (\bibinfo{year}{1972}).

[\citenamefont{Ferrari and Mashhoon}, 1984]
\bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{Ferrari}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{B.}~\bibnamefont{Mashhoon}},
\bibinfo{journal}{Phys. Rev.} \textbf{\bibinfo{volume}{D30}},
\bibinfo{pages}{295} (\bibinfo{year}{1984}{\natexlab{a}}).

[\citenamefont{Ferrari and Mashhoon}, 1984]
\bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{Ferrari}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{B.}~\bibnamefont{Mashhoon}},
\bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{52}},
\bibinfo{pages}{1361} (\bibinfo{year}{1984}{\natexlab{b}}).

[\citenamefont{Mashhoon}, 1985]
\bibinfo{author}{\bibfnamefont{B.}~\bibnamefont{Mashhoon}},
\bibinfo{journal}{Phys. Rev.} \textbf{\bibinfo{volume}{D31}},
\bibinfo{pages}{290} (\bibinfo{year}{1985}).

[\citenamefont{Bombelli and Calzetta}, 1992]
\bibinfo{author}{\bibfnamefont{L.}~\bibnamefont{Bombelli}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Calzetta}},
\bibinfo{journal}{Class. Quant. Grav.} \textbf{\bibinfo{volume}{9}},
\bibinfo{pages}{2573} (\bibinfo{year}{1992}).

[\citenamefont{Cornish and Levin}, 2003]
\bibinfo{author}{\bibfnamefont{N.~J.} \bibnamefont{Cornish}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~J.} \bibnamefont{Levin}},
\bibinfo{journal}{Class. Quant. Grav.} \textbf{\bibinfo{volume}{20}},
\bibinfo{pages}{1649} (\bibinfo{year}{2003}), \eprint{gr-qc/0304056}.

[\citenamefont{Cardoso et~al.}, 2009]
\bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{Cardoso}},
\bibinfo{author}{\bibfnamefont{A.~S.} \bibnamefont{Miranda}},
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Berti}},
\bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Witek}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{V.~T.} \bibnamefont{Zanchin}},
\bibinfo{journal}{Phys. Rev.} \textbf{\bibinfo{volume}{D79}},
\bibinfo{pages}{064016} (\bibinfo{year}{2009}), \eprint{0812.1806}.

[\citenamefont{Dolan}, 2010]
\bibinfo{author}{\bibfnamefont{S.~R.} \bibnamefont{Dolan}},
\bibinfo{journal}{Phys. Rev.} \textbf{\bibinfo{volume}{D82}},
\bibinfo{pages}{104003} (\bibinfo{year}{2010}), \eprint{1007.5097}.

[\citenamefont{Yang et~al.}, 2012]
\bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Yang}},
\bibinfo{author}{\bibfnamefont{D.~A.} \bibnamefont{Nichols}},
\bibinfo{author}{\bibfnamefont{F.}~\bibnamefont{Zhang}},
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Zimmerman}},
\bibinfo{author}{\bibfnamefont{Z.}~\bibnamefont{Zhang}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{Y.}~\bibnamefont{Chen}},
\bibinfo{journal}{Phys. Rev.} \textbf{\bibinfo{volume}{D86}},
\bibinfo{pages}{104006} (\bibinfo{year}{2012}), \eprint{1207.4253}.

[\citenamefont{Stuchlik and Calvani}, 1991]
\bibinfo{author}{\bibfnamefont{Z.}~\bibnamefont{Stuchlik}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Calvani}},
\bibinfo{journal}{General Relativity and Gravitation}
\textbf{\bibinfo{volume}{23}}, \bibinfo{pages}{507} (\bibinfo{year}{1991}),
ISSN \bibinfo{issn}{1572-9532},
\urlprefix\url{https://doi.org/10.1007/BF00758012}.

[\citenamefont{Zimmerman and Mark}, 2016]
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Zimmerman}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{Z.}~\bibnamefont{Mark}},
\bibinfo{journal}{Phys. Rev. D} \textbf{\bibinfo{volume}{93}},
\bibinfo{pages}{044033} (\bibinfo{year}{2016}), \bibinfo{note}{[Erratum:
Phys.Rev.D 93, 089905 (2016)]}, \eprint{1512.02247}.

[46]
\bibinfo{author}{\bibfnamefont{O.~J.~C.} \bibnamefont{Dias}},
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Godazgar}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibinfo{journal}{in preparation (2021)}  (????).

[\citenamefont{Bardeen and Horowitz}, 1999]
\bibinfo{author}{\bibfnamefont{J.~M.} \bibnamefont{Bardeen}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{G.~T.} \bibnamefont{Horowitz}},
\bibinfo{journal}{Phys. Rev. D} \textbf{\bibinfo{volume}{60}},
\bibinfo{pages}{104030} (\bibinfo{year}{1999}), \eprint{hep-th/9905099}.

[\citenamefont{Yang et~al.}, 2013]
\bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Yang}},
\bibinfo{author}{\bibfnamefont{F.}~\bibnamefont{Zhang}},
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Zimmerman}},
\bibinfo{author}{\bibfnamefont{D.~A.} \bibnamefont{Nichols}},
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Berti}},
\bibnamefont{et~al.}, \bibinfo{journal}{Phys.Rev.}
\textbf{\bibinfo{volume}{D87}}, \bibinfo{pages}{041502}
(\bibinfo{year}{2013}{\natexlab{a}}), \eprint{1212.3271}.

[\citenamefont{Yang et~al.}, 2013]
\bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Yang}},
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Zimmerman}},
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Zenginoğlu}},
\bibinfo{author}{\bibfnamefont{F.}~\bibnamefont{Zhang}},
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Berti}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{Y.}~\bibnamefont{Chen}},
\bibinfo{journal}{Phys. Rev.} \textbf{\bibinfo{volume}{D88}},
\bibinfo{pages}{044047} (\bibinfo{year}{2013}{\natexlab{b}}),
\bibinfo{note}{[Phys. Rev.D88,044047(2013)]}, \eprint{1307.8086}.

[\citenamefont{Kittel}, 2004]
\bibinfo{author}{\bibfnamefont{C.}~\bibnamefont{Kittel}},
\emph{\bibinfo{title}{Introduction to solid state physics}}
(\bibinfo{publisher}{John Wiley \& Sons (8th ed.)}, \bibinfo{year}{2004}).

[51]
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Robinson}},
\bibinfo{journal}{in {``The Kerr Spacetime: Rotating Black Holes in General
Relativity."}}  (\bibinfo{year}{Editors: D. L. Wiltshire, M. Visser, S. M.
Scott (Cambridge University Press, 2009).}).

[\citenamefont{Chrusciel et~al.}, 2012]
\bibinfo{author}{\bibfnamefont{P.~T.} \bibnamefont{Chrusciel}},
\bibinfo{author}{\bibfnamefont{J.~L.} \bibnamefont{Costa}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Heusler}},
\bibinfo{journal}{Living Rev.Rel.} \textbf{\bibinfo{volume}{15}},
\bibinfo{pages}{7} (\bibinfo{year}{2012}), \eprint{1205.6112}.

[\citenamefont{Newman et~al.}, 1965]
\bibinfo{author}{\bibfnamefont{E.~T.} \bibnamefont{Newman}},
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Couch}},
\bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Chinnapared}},
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Exton}},
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Prakash}},
\bibnamefont{et~al.}, \bibinfo{journal}{J.Math.Phys.}
\textbf{\bibinfo{volume}{6}}, \bibinfo{pages}{918} (\bibinfo{year}{1965}).

[\citenamefont{Newman and Penrose}, 1962]
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Newman}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Penrose}},
\bibinfo{journal}{J.Math.Phys.} \textbf{\bibinfo{volume}{3}},
\bibinfo{pages}{566} (\bibinfo{year}{1962}).

[\citenamefont{Stephani et~al.}, 2003]
\bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Stephani}},
\bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Kramer}},
\bibinfo{author}{\bibfnamefont{M.~A.} \bibnamefont{MacCallum}},
\bibinfo{author}{\bibfnamefont{C.}~\bibnamefont{Hoenselaers}},
\bibnamefont{and} \bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Herlt}},
\emph{\bibinfo{title}{Exact solutions of Einstein's field equations}}
(\bibinfo{publisher}{CUP}, \bibinfo{year}{2003}).

[\citenamefont{Teukolsky}, 1972]
\bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Teukolsky}},
\bibinfo{journal}{Phys.Rev.Lett.} \textbf{\bibinfo{volume}{29}},
\bibinfo{pages}{1114} (\bibinfo{year}{1972}).

[\citenamefont{Regge and Wheeler}, 1957]
\bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Regge}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~A.} \bibnamefont{Wheeler}},
\bibinfo{journal}{Phys.Rev.} \textbf{\bibinfo{volume}{108}},
\bibinfo{pages}{1063} (\bibinfo{year}{1957}).

[\citenamefont{Zerilli}, 1974]
\bibinfo{author}{\bibfnamefont{F.}~\bibnamefont{Zerilli}},
\bibinfo{journal}{Phys.Rev.} \textbf{\bibinfo{volume}{D9}},
\bibinfo{pages}{860} (\bibinfo{year}{1974}).

[\citenamefont{Berti et~al.}, 2009]
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Berti}},
\bibinfo{author}{\bibfnamefont{V.}~\bibnamefont{Cardoso}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{A.~O.} \bibnamefont{Starinets}},
\bibinfo{journal}{Classical and Quantum Gravity}
\textbf{\bibinfo{volume}{26}}, \bibinfo{pages}{163001}
\urlprefix\url{https://doi.org/10.1088/0264-9381/26/16/163001}.

[\citenamefont{Onozawa}, 1997]
\bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Onozawa}},
\bibinfo{journal}{Physical Review D} \textbf{\bibinfo{volume}{55}},
\bibinfo{pages}{3593–3602} (\bibinfo{year}{1997}), ISSN
\bibinfo{issn}{1089-4918},
\urlprefix\url{http://dx.doi.org/10.1103/PhysRevD.55.3593}.

[\citenamefont{Dias and Santos}, 2020]
\bibinfo{author}{\bibfnamefont{O.~J.~C.} \bibnamefont{Dias}} \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{J.~E.} \bibnamefont{Santos}},
\bibinfo{journal}{Phys. Rev. D} \textbf{\bibinfo{volume}{102}},
\bibinfo{pages}{124039} (\bibinfo{year}{2020}), \eprint{2005.03673}.

[\citenamefont{Geroch et~al.}, 1973]
\bibinfo{author}{\bibfnamefont{R.~P.} \bibnamefont{Geroch}},
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Held}}, \bibnamefont{and}
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Penrose}},
\bibinfo{journal}{J.Math.Phys.} \textbf{\bibinfo{volume}{14}},
\bibinfo{pages}{874} (\bibinfo{year}{1973}).

\end{thebibliography}
\bibliographystyle{apsrev}

\end{document}


11institutetext:  Istanbul Technical University, Istanbul, Turkey
11email: {yesilkaynak15, sahinyu<EMAIL_ADDRESS>

# EfficientSeg: An Efficient Semantic Segmentation Network

Vahit Bugra Yesilkaynak  Yusuf H. Sahin  Gozde Unal

###### Abstract

Deep neural network training without pre-trained weights and few data is shown
to need more training iterations. It is also known that, deeper models are
more successful than their shallow counterparts for semantic segmentation
task. Thus, we introduce EfficientSeg architecture, a modified and scalable
version of U-Net, which can be efficiently trained despite its depth. We
evaluated EfficientSeg architecture on Minicity dataset and outperformed U-Net
baseline score ($40\%$ mIoU) using the same parameter count ($51.5\%$ mIoU).
Our most successful model obtained $58.1\%$ mIoU score and got the fourth
place in semantic segmentation track of ECCV 2020 VIPriors challenge.

###### Keywords:

semantic segmentation, few data, MobileNet, data efficiency

##  1 Introduction

Typical machine learning approaches, especially deep learning, draw its
strength from the usage of a high number of supervised examples[15]. However,
reliance on large training sets restricts the applicability of deep learning
solutions to various problems where high amounts of data may not be available.
Thus, generally in few shot learning approaches, it is very common to start
the network training using a pre-trained network or network backbone to obtain
prior knowledge [24] from a larger dataset like ImageNet[5]. However, for the
tasks defined on domains that are different from that of natural images such
as for medical image segmentation [19, 13], it is not meaningful to start from
pre-trained weights. This distinction makes learning from scratch using a low
number of data instances, an important objective. This is also the objective
of the newly emerging data-efficient deep learning field.

In [7], the authors argued that, non-pre-trained models can perform similar to
their pre-trained counterparts even if it takes more iterations and/or fewer
data to train. Also in [26], it is shown that, with stronger data augmentation
the need to pre-train the network lessens. Even when using pre-trained
networks, there is strong evidence that data augmentation improves the results
[10, 17, 2].

In semantic segmentation, it is known that building deeper networks or using
deeper backbones affects the results positively [8, 16]. Yet deeper networks
come with limitations. Ideally, a baseline network which is subject to scaling
should be memory and time-efficient. The latter is due to the fact that the
number of needed training iterations will be increased for a large network.
Using MobileNetV3[9] blocks, we are able to create a baseline model which is
still expressive and deep with a lower parameter count. Regarding all these
considerations, in this article, we present a new deep learning architecture
for segmentation, using MobileNetV3 blocks. As we focused on the problem of
training with few data, we evaluated our network in Minicity
dataset111https://github.com/VIPriors/vipriors-challenges-
toolkit/tree/master/semantic-segmentation, which is a subset of Cityscapes
[3]. Our method obtained the fourth place in the semantic segmentation
challenge on ECCV VIPriors workshop 222https://vipriors.github.io/challenges/.

##  2 Related Work

Semantic Segmentation. Computer vision problems focus on extracting useful
information from images automatically such as classifying objects, detecting
objects, estimating pose and so on. Semantic segmentation is one such problem
where the main concern is to group the pixels on an image to state what pixels
belong to which entity in the image. Semantic segmentation finds many
applications in real life problems yet we can divide the efforts on the field
into two main categories: offline segmentation and real-time segmentation.
Real-time segmentation networks need to be both fast and accurate, with this
constraint they generally have lower mIoU compared to their counter-parts. To
our knowledge currently the state-of-the-art is U-HarDNet-70[1] with reported
75.9% class mIoU and 53 frames per second with a 1080Ti GPU. On the other
hand, offline segmentation has no time concerns thus the proposed solutions
are generally slower. To our knowledge, the state of the art technique on
offline Cityscapes segmentation is HRNet-OCR[23] with a class mIoU of 85.1%.
We next describe the most popular architectural paradigm in image recognition,
namely the MobileNet.

MobileNet Blocks. With the increasing popularity of CNNs, the demand on easy-
to-access applications based on CNNs have also increased. One way to establish
the demanded accessibility is to use mobile devices, yet the competition on
image recognition challenges generally pushed CNN networks into being too big
to run on mobile devices. In this environment, there are two main solutions to
make mobile CNN applications feasible: running the networks in powerful
servers for external computation or using smaller networks to fit in mobile
devices. In this paper, we focus on the second solution, which aims at
creating smaller networks. Howard et al. introduced a family of networks
called MobileNets[10] with this motivation. The main idea behind MobileNets is
utilizing Depthwise Separable Convolutional (DSC) layers. DSC layer is very
much like a standard 2D convolutional layer and serves the same purpose yet it
is both smaller in number of parameters and faster compared to its
counterpart. Figure 1 depicts the difference between a standard convolution
layer and DSC layer. MobileNet architecture has two more improved versions
namely MobileNetV2[20] and MobileNetV3[9], before going into the details of
MobileNetV3, we describe MobileNetV2 and another work based on it,
EfficientNet[22].

MobileNetV2 Blocks and EfficientNet. MobileNetV2 relies on two main
components: depthwise separable convolutional layers and inverted residual
architecture with linear bottlenecks. Inverted residual architecture is
implemented by adding a middle phase called expansion phase, inside
MobileNetV2 blocks the input tensor are expanded into having $t\times d$ depth
with a convolution operation $t$ and $d$ are expansion ratio and depth of the
input tensor respectively, after the expansion phase depthwise separable
convolution phase follows. EfficientNets[22] are a family of networks which
was built to be small, fast and accurate on image classification task. It
consists of blocks pretty similar to MobileNetV2, yet instead of making the
networks mobile, the authors used the advantages of MobileNetV2 blocks to
create bigger networks, namely EfficientNets, are have significantly smaller
number of parameters compared to their similar performing counterparts thus
they are both memory and time efficient. After the success EfficientNet has
achieved, Howard et al. published another work which is called MobileNetV3[9].

Figure 1: Figure shows the difference between a standard convolution layer (a)
and a depthwise separable convolution layer (b), depthwise separable layer
consists of two convolution operations which decreases the number of
parameters. In the figure ”k” is the kernel size and ”d” is the depth of the
input tensor.

MobileNetV3. We use MobileNetV3 as the building blocks of our network
EfficientSeg. Howard et al. added a Squeeze-and-Excite[11] operation to the
residual layer and introduced a new architecture scheme. In our work we use
this architecture to create a U-shaped semantic segmentation network. We will
discuss further details in the following sections.

Data augmentation. As stated in Section 1, data augmentation is important for
learning from few data. In traditional neural network training,
transformations like flipping, cropping, scaling and rotating are highly used.
In [18], [4] and [12] more complex data augmentation methods like JPEG
compression, local copying of segmentation masks, contrast, brightness and
sharpness changes, blurring are suggested. There are also data augmentation
methods focusing on generating new data by GANs or style transfer[25, 21, 6],
but they are out of scope for the Minicity segmentation task since they are
not generally applicable for training from scratch.

##  3 Method

In this paper, we present a new neural architecture called EfficientSeg, which
can be counted as a modified version of the classic U-Net architecture[19] by
alternating the blocks with inverted residual blocks which are presented in
MobileNetV3[9].

The EfficientSeg network, which is illustrated in Figure 2, is a U-shaped
architecture with 4 concatenation shortcuts, between an encoder and a decoder.
Our encoder which is the down-sampling encoding branch of the network is like
a MobileNetV3-Large classifier itself without the classification layers,
whereas the decoder is its mirror symmetric version, where the down-sampling
is replaced with upsampling operation. In the decoder part, we need to
upsample the input tensors to retrieve a segmentation mask image which is the
same size as the input image. We apply an upsample with bilinear interpolation
and a scale factor 2 at each block where its symmetric is a downsample block
on the encoder side.

We have 4 shortcut connections across from the encoder towards the decoder at
the same layer. Each shortcut is done by concatenating the input of a
downsampling block in the encoder part with the corresponding upsampled output
in the decoder part. In this way, we enable the network to capture the fine
details through these shortcuts rather than solely preserving them in the
bottleneck.

As in MobileNetV3 blocks, a width scaling parameter to upscale the network
also exists in EfficientSeg, making it suitable to create networks of
different scales. We will be discussing two of them which are EfficientSeg
(1.5) which has the same number of parameters as baseline the U-Net in
Minicity Challenge and also our larger network EfficientSeg (6.0).

Figure 2: EfficientSeg architecture. There are 5 different type of blocks.
Inverted Residual Blocks are MobileNetV3 blocks described as in the paper. 1x1
and 3x3 blocks are standard convolution blocks which has activation and batch
normalization. Downsampling operations are done with increasing the stride and
for upsampling, linear interpolation is used.

##  4 Experiment

In our experiments, we train the EfficientSeg network with $384\times 768$
sized cropped images using Adam[14] optimization algorithm with a learning
rate of lr=1e-3 at the start. We divide the learning rate by 10 at $200^{th}$
and $400^{th}$ epochs. As the objective function, we use a weighted cross-
entropy loss. In the dataset, we observe that some of the categories are
underrepresented relative to the others. We incorporate that information into
the objective function in the form of increased weights: a weight of 2 (wall,
fence, pole, rider, motorcycle, bicycle) and a weight of 3(bus, train, truck)
are used for the rare classes. For every epoch, 20 extra images for each rare
class are also fed to the network.

Deciding on which data augmentations to use requires prior knowledge of the
domain [4]. Since in our train set we have few objects of same category having
different color and texture properties, we decided to reduce the texture
dependency and increase the color invariance by (i) multiplying hue and
brightness values of the image by uniformly distributed random values in
($0.4,1.6$), and (ii) JPEG compression. We also did (iii) non-uniform scaling,
(iv) random rotation ($\pm 20^{\circ}$) and (v) flipping as in standard deep
learning approaches. At evaluation time, we feed the network with both the
original test images and their flipped versions, then calculate average of
their scores to obtain the final segmentation.

Utilizing nearly the same parameter count by using a depth parameter of 1.5,
we obtain an mIoU score of $51.5\%$ on the test set whereas baseline U-Net
model has a score of $40\%$. To further improve the model we also tested with
a depth parameter of 6.0 and obtain an improved mIoU result of $58.1\%$. To
demonstrate the importance of texture based data augmentation, we also train
the network without the aforementioned augmentations. As can be seen in Table
1, using both the aforementioned augmentation strategy and increasing the
depth of the network, we obtain our highest score. Our code for these
experiments is publicly available333https://github.com/MrGranddy/EfficientSeg.

| EfficientSeg (1.5) |  | EfficientSeg (6.0)
---
w/o aug.
EfficientSeg (6.0) |
road | 0.960 | 0.954 | 0.962 |
sidewalk | 0.707 | 0.685 | 0.738 |
building | 0.846 | 0.832 | 0.864 |
wall | 0.277 | 0.165 | 0.318 |
fence | 0.285 | 0.197 | 0.304 |
pole | 0.449 | 0.471 | 0.517 |
traffic light | 0.239 | 0.382 | 0.450 |
traffic sign | 0.491 | 0.517 | 0.615 |
vegetation | 0.885 | 0.888 | 0.899 |
terrain | 0.501 | 0.464 | 0.576 |
sky | 0.912 | 0.919 | 0.932 |
person | 0.580 | 0.575 | 0.710 |
rider | 0.222 | 0.179 | 0.353 |
car | 0.864 | 0.842 | 0.899 |
truck | 0.342 | 0.106 | 0.497 |
bus | 0.264 | 0.128 | 0.325 |
train | 0.169 | 0.002 | 0.137 |
motorcycle | 0.278 | 0.191 | 0.333 |
bicycle | 0.518 | 0.544 | 0.611 |
mIoU | 0.515 | 0.476 | 0.581 |
Table 1: Class IoU and mIoU scores on Minicity test set for differently
trained EfficientSeg architectures

It is also worth mentioning that, the effect of the aforementioned data
augmentation techniques, is more significant than depth up-scaling. This
result empirically shows the importance of texture based data augmentation.

##  5 Conclusions

In conclusion, we introduced a novel semantic segmentation architecture
EfficientSeg which consists of scalable blocks to make it easy to fit for
problems of different scales. In our work we empirically show how selecting
the most beneficial augmentation improves the success of the network, making
it even more advantageous than up-scaling the network. When trained with our
augmentation set EfficientSeg (1.5) achieves 51.5% mIoU, outperforming its
much larger counterpart EfficientSeg (6.0) if no augmentation is applied, in
the other hand when trained with our augmentation set we achieve our best
score 58.1%. Utilizing prior knowledge is especially important on tasks
providing few data to train on, as the popularity of efficient image
recognition networks increases, it is expected that data efficiency is the
next step to have simple, efficient and elegant solutions to image recognition
tasks.

## References

  * [1] Chao, P., Kao, C.Y., Ruan, Y.S., Huang, C.H., Lin, Y.L.: Hardnet: A low memory traffic network (2019)
  * [2] Chen, L.C., Papandreou, G., Schroff, F., Adam, H.: Rethinking atrous convolution for semantic image segmentation. arXiv preprint arXiv:1706.05587 (2017)
  * [3] Cordts, M., Omran, M., Ramos, S., Rehfeld, T., Enzweiler, M., Benenson, R., Franke, U., Roth, S., Schiele, B.: The cityscapes dataset for semantic urban scene understanding. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 3213–3223 (2016)
  * [4] Cubuk, E.D., Zoph, B., Shlens, J., Le, Q.V.: Randaugment: Practical automated data augmentation with a reduced search space. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops. pp. 702–703 (2020)
  * [5] Deng, J., Dong, W., Socher, R., Li, L.J., Li, K., Fei-Fei, L.: ImageNet: A Large-Scale Hierarchical Image Database. In: CVPR09 (2009)
  * [6] Frid-Adar, M., Diamant, I., Klang, E., Amitai, M., Goldberger, J., Greenspan, H.: Gan-based synthetic medical image augmentation for increased cnn performance in liver lesion classification. Neurocomputing 321, 321–331 (2018)
  * [7] He, K., Girshick, R., Dollár, P.: Rethinking imagenet pre-training. In: Proceedings of the IEEE international conference on computer vision. pp. 4918–4927 (2019)
  * [8] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770–778 (2016)
  * [9] Howard, A., Sandler, M., Chu, G., Chen, L., Chen, B., Tan, M., Wang, W., Zhu, Y., Pang, R., Vasudevan, V., Le, Q.V., Adam, H.: Searching for mobilenetv3. CoRR abs/1905.02244 (2019), http://arxiv.org/abs/1905.02244
  * [10] Howard, A.G.: Some improvements on deep convolutional neural network based image classification. arXiv preprint arXiv:1312.5402 (2013)
  * [11] Hu, J., Shen, L., Sun, G.: Squeeze-and-excitation networks. CoRR abs/1709.01507 (2017), http://arxiv.org/abs/1709.01507
  * [12] Jung, A.B., Wada, K., Crall, J., Tanaka, S., Graving, J., Reinders, C., Yadav, S., Banerjee, J., Vecsei, G., Kraft, A., Rui, Z., Borovec, J., Vallentin, C., Zhydenko, S., Pfeiffer, K., Cook, B., Fernández, I., De Rainville, F.M., Weng, C.H., Ayala-Acevedo, A., Meudec, R., Laporte, M., et al.: imgaug. https://github.com/aleju/imgaug (2020), online; accessed 01-Feb-2020
  * [13] Kamnitsas, K., Ledig, C., Newcombe, V.F., Simpson, J.P., Kane, A.D., Menon, D.K., Rueckert, D., Glocker, B.: Efficient multi-scale 3d cnn with fully connected crf for accurate brain lesion segmentation. Medical image analysis 36, 61–78 (2017)
  * [14] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
  * [15] Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: Pereira, F., Burges, C.J.C., Bottou, L., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems 25, pp. 1097–1105. Curran Associates, Inc. (2012), http://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf
  * [16] Li, X., Zhang, L., You, A., Yang, M., Yang, K., Tong, Y.: Global aggregation then local distribution in fully convolutional networks. arXiv preprint arXiv:1909.07229 (2019)
  * [17] Long, J., Shelhamer, E., Darrell, T.: Fully convolutional networks for semantic segmentation. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 3431–3440 (2015)
  * [18] Ma, R., Tao, P., Tang, H.: Optimizing data augmentation for semantic segmentation on small-scale dataset. In: Proceedings of the 2nd International Conference on Control and Computer Vision. pp. 77–81 (2019)
  * [19] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: International Conference on Medical image computing and computer-assisted intervention. pp. 234–241. Springer (2015)
  * [20] Sandler, M., Howard, A.G., Zhu, M., Zhmoginov, A., Chen, L.: Inverted residuals and linear bottlenecks: Mobile networks for classification, detection and segmentation. CoRR abs/1801.04381 (2018), http://arxiv.org/abs/1801.04381
  * [21] dos Santos Tanaka, F.H.K., Aranha, C.: Data augmentation using gans. CoRR abs/1904.09135 (2019), http://arxiv.org/abs/1904.09135
  * [22] Tan, M., Le, Q.V.: Efficientnet: Rethinking model scaling for convolutional neural networks. CoRR abs/1905.11946 (2019), http://arxiv.org/abs/1905.11946
  * [23] Tao, A., Sapra, K., Catanzaro, B.: Hierarchical multi-scale attention for semantic segmentation (2020)
  * [24] Wang, Y., Yao, Q., Kwok, J.T., Ni, L.M.: Generalizing from a few examples: A survey on few-shot learning. ACM Computing Surveys (CSUR) 53(3), 1–34 (2020)
  * [25] Zhu, X., Liu, Y., Qin, Z., Li, J.: Data augmentation in emotion classification using generative adversarial networks. arXiv preprint arXiv:1711.00648 (2017)
  * [26] Zoph, B., Ghiasi, G., Lin, T.Y., Cui, Y., Liu, H., Cubuk, E.D., Le, Q.V.: Rethinking pre-training and self-training. arXiv preprint arXiv:2006.06882 (2020)