# Image quality measurements and denoising using
Fourier Ring Correlations

J. Kaczmar-Michalska∗†‡, N. R. Hajizadeh∗, A.J. Rzepiela∗⋄ and S.F.
Nørrelykke∗⋄
⋄Correspondence to<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
∗Scientific Center for Optical and Electron Microscopy (ScopeM),
Eidgenössische Technische Hohschule Zürich, (ETH Zurich), 8093 Zürich,
Switzerland
†TOOPLOOX, 53-601 Wrocław, Poland
‡Wrocław University of Science and Technology, 50-370 Wrocław, Poland

###### Abstract

Image quality is a nebulous concept with different meanings to different
people. To quantify image quality a relative difference is typically
calculated between a corrupted image and a ground truth image. But what metric
should we use for measuring this difference? Ideally, the metric should
perform well for both natural and scientific images. The structural similarity
index (SSIM) is a good measure for how humans perceive image similarities, but
is not sensitive to differences that are scientifically meaningful in
microscopy. In electron and super-resolution microscopy, the Fourier Ring
Correlation (FRC) is often used, but is little known outside of these fields.
Here we show that the FRC can equally well be applied to natural images, e.g.
the Google Open Images dataset. We then define a loss function based on the
FRC, show that it is analytically differentiable, and use it to train a U-net
for denoising of images. This FRC-based loss function allows the network to
train faster and achieve similar or better results than when using
$\mathrm{L_{1}}$\- or $\mathrm{L_{2}}$-based losses. We also investigate the
properties and limitations of neural network denoising with the FRC analysis.

##  1 INTRODUCTION

###  1.1 Neural networks for image denoising

One of the most fundamental problems in image processing is that of image
denoising, formulated as recovering a high quality image from its noisy
(degraded) realisation. Denoising methods can be grouped into traditional
methods—including spatial and frequency based filtering as well as wavelet
transform-based methods [32], BM3D being a well known example [6]—and the more
recent machine learning based approaches, mainly the broad family of
convolutional neural network (CNN) models.

Traditional methods often rely on prior knowledge and explicit assumptions
about the character of the corruption, whereas learning-based approaches are
more data-driven and learn to differentiate the signal from the noise by
seeing a large number of examples. Following the rapid development of deep
learning over the past decade, there have been a multitude of deep learning
denoising models proposed, for instance DnCNN [33], FFDNet for blind denoising
(when the noise level is unknown) [34], BRDNET [24], and U-NET based models
[31] to name but a few. Over the last few years, several deep learning
approaches were introduced that eliminated the need for ground truth data
(GT), with the most prominent being Noise2Noise (N2N) [16] which recovers
signals under different types of corruptions, from pairs of corrupted images,
if the expectation of the corrupted data is the same as the clean target. N2N
gives state of the art performance [2], but requires a setup where a target is
measured a several times (independent noise realizations).

Figure 1: $\mathbf{A}$, an image and $\mathbf{B}$, $\log_{2}$ magnitudes of
its power spectral density in 2D Fourier space with three examples of
concentric rings (white), as used to calculate the Fourier ring correlation
(FRC) values. The low frequency information with high magnitudes is in the
center of the transformed image.

More recently, the focus has shifted towards improving denoising with only a
single corrupted image as input, and several networks such as Noise2Void [12]
or Noise2Self (N2S) [2] have been proposed. During training, these methods
systematically remove/mask parts of the input, e.g. the center pixel, and
infer the pixel value from just its neighbourhood. In probabilistic
unsupervised denoising, a noise model is incorporated in the process, in order
to refine the posterior distribution of the signal. The noise model can be
created either non-parametrically through sampling examples [13, 19], or by
bootstrapping existing data and formulating the noise model, for example as a
Gaussian mixture model (GMM) or Gaussian/Poisson noise model [15]. These
denoisers outperform their simpler counterparts (N2S) and achieve performance
comparable to training schemes with the ground truth available. Last, but not
least, the DivNoising network explicitly samples from an approximate posterior
of possible true signals obtained by using a variational autoencoder and
generates an ensemble of possible predictions for the denoised image [18].
This approach both highlights and explicitly addresses the inherent ambiguity
in the denoising problem.

###  1.2 Denoising metrics

A concept directly relevant to image denoising, and in particular learning
based approaches, is the score or metric. Here we use ”metric” not in the
mathematical sense of a distance function, but simply to refer to the function
used to calculate the difference between two images or the quality or
resolution of a single image; we use ”loss” to refer to the function used to
train a network. The metric and the loss can be the same function.

The most widely used metric and loss for image denoising with neural networks
is the mean squared error (MSE) [35], also called the $\mathcal{L}_{2}$ loss,
which is based on the pixel-wise difference between two images. If $I$ and $J$
are monochrome images of size $M\times N$, then the MSE is defined as follows

$\mathcal{L}_{2}(I,J)\equiv\mathrm{MSE}=\frac{1}{MN}\sum_{m=0}^{M-1}\sum_{n=0}^{N-1}\left[I_{m,n}-J_{m,n}\right]^{2}\enspace,$
(1)

where $m,n$ are discrete pixel coordinates. It is therefore a representation
of absolute error, where values closer to zero indicate a higher quality. The
use of MSE assumes that the impact of noise is independent of the local
characteristics of the image, and implicitly assumes a Gaussian noise model. A
related metric for image quality assessment is the peak-signal to noise ratio
(PSNR), which is defined in terms of the MSE as

$\mathrm{PSNR(I,J)}\equiv
10\log_{10}\left(\frac{\max^{2}(I)}{\mathrm{MSE}(I,J)}\right)\enspace,$ (2)

where $\max(I)$ is the maximum (the peak) possible value of the clean (signal)
image, e.g. 255 for an 8-bit image, the MSE is a measure of the noise that
separates $I$ and $J$, and the ratio is measured in decibel. Both the MSE and
PSNR are straightforward to determine and are physically intuitive as metrics.
However, they often do not correlate well with perceived image quality [30].
Complementary approaches for assessing image quality exist, such as the
structural similarity index (SSIM) [29], and more recently its multi-scale
variant (MS-SSIM) [30], with the latter being the most successful image metric
in terms of mimicking human judgement. However, in the context of quantifying
signal from images, e.g. scientific images, mimicking human judgement is not
the absolute priority.

In the field of electron microscopy, where high voltage electrons are used to
image materials, a metric based on the correlation of images in Fourier space,
the Fourier Ring Correlation (FRC) [27, 23] and its 3D variant Fourier Shell
Correlation (FSC) [9], has been in use since their introduction in the 80ies.
The FRC’s original intended use was to estimate resolution from images, and
their 3D models, of proteins acquired by single particle cryo-electron
microscopy [28]. The FRC and some closely related measures have, however, also
found recent application in other fields, for example in the fluorescence and
super-resolution microscopy communities, where they are used for image
restoration [11] and reconstruction [3], measuring resolution [1, 7], and
detecting optical artifacts [4].

The FRC/FSC is based on a normalized cross-correlation between two images,
calculated in the frequency domain. The calculation starts with dividing the
spatial frequency spectra of the two images into a series of concentric rings,
see Figure 1. The FRC value, a scalar, of each ring is calculated like this

$\mathrm{FRC}(I,J;r)\equiv\frac{\sum_{S}\mathcal{F}_{p,q}\,\mathcal{G}^{*}_{p,q}}{\sqrt{\sum_{S}|\mathcal{F}_{p,q}|^{2}\;\sum_{S}|\mathcal{G}_{p,q}|^{2}}}$
(3)

where $S$ is the set of coordinates where $p^{2}+q^{2}=r^{2}$, i.e., a ring of
radius $r$ in Fourier space, ∗ denotes complex conjugation, $\mathcal{F}$ is
the discrete 2D Fourier transforms of image $I$

$\mathcal{F}_{p,q}\equiv\tilde{I}_{p,q}=\sum_{m=0}^{M-1}\sum_{n=0}^{N-1}I_{m,n}\,e^{-i2\pi(pm/M+qn/N)}\enspace,$
(4)

and an analogous expression holds for $\mathcal{G}$, the transform of $J.$ The
sum in the numerator of the FRC is real, as explained in [26], since Fourier
transforms of images exhibit Friedel symmetry and pixels placed on opposite
sides of the frequency ring form conjugate pairs. The maximal number of
complete rings for a $N\times N$ digital image is $\frac{N}{2}$, following the
Nyquist frequency sampling criterion. Higher frequency rings, up to
$\frac{N}{\sqrt{2}}$, are also partially present. The FRC takes on values
between $+1$, the value found when comparing two identical images (perfect
correlation), and $-1$ (anti-correlation) for comparing an image and its
inverted copy. For noisy images the lower limit is $0$ (uncorrelated), when
e.g. noise is compared to a ground truth image. In practice, the FRC is often
calculated in non-overlapping annuli of thickness larger than one, i.e. a
larger band of frequencies are included for each FRC value, mostly to suppress
fluctuations. Some useful mathematical properties and limit behaviors of the
FRC are derived in section 2.

###  1.3 Aim and approach

Here we build on the results of [11] in terms of translating the use of FRC as
a resolution assessment to also be used in the wider context of image
denoising and image quality assessment. Our contributions are three-fold.

First, we derive some mathematical facts of the FRC: Its analytic
differentiability, limit properties, and invariant behaviour in a number of
common scenarios, such as image-scaling, additive noise, and spatial
filtering.

Next, we show that the FRC can be used for assessing image quality, more
specifically we show that it constitutes a highly informative quality metric
for natural images with performance on par with SSIM, but with the additional
advantage of providing the quality score as a function of signal frequency.
Previous works have highlighted the importance of combining numerical and
graphical measures to judge image quality, and that a single scalar value is
not sufficient to comprehensively assess the range of degradations [8].

Then, we showcase how the FRC can be used to define a loss function for neural
network training, and provide its application for denoising tasks on different
noise types. Networks trained with the FRC-based loss, train faster due to its
gradient shape, and can denoise several types of degradations.

Finally, with the help of the FRC metric, we make observations on the
characteristics of image denoising. In section 3.4 we show how denoising
performance correlates with the power spectrum of the images, i.e. exhibiting
greater performance on frequencies with higher signal.

##  2 Theory

###  2.1 Differentiability of the FRC-loss

Having defined the FRC in Eq. (3) we introduce the FRC-loss as the sum over
all annuli:

$\mathcal{L}_{\mathrm{FRC}}(I,J)\equiv 1-\sum_{r}\mathrm{FRC}(I,J;r)$ (5)

Consider the FRC-loss $\mathcal{L}_{\mathrm{FRC}}$ as defined in Eq. (5) but
rewritten, simplifying notation by suppressing dependence on $I$ and $J$, as

$\mathcal{L}_{\mathrm{FRC}}=1-\sum_{r}\frac{A(r)}{B(r)}$ (6)

with

$\displaystyle A(r)$
$\displaystyle=\sum_{S}\mathcal{F}_{p,q}\,\mathcal{G}^{*}_{p,q}$ (7)
$\displaystyle B(r)$
$\displaystyle=\sqrt{\sum_{S}|\mathcal{F}_{p,q}|^{2}\;\sum_{S}|\mathcal{G}_{p,q}|^{2}}\enspace.$
(8)

Now, $\mathcal{L}_{\mathrm{FRC}}$ is a sum of terms (plus a constant), so if
each term is differentiable, then so is the sum, i.e., we can focus on the
differentiability of the FRC itself. This again reduces to three steps, namely
to showing that $A$, $B$, and $A/B$ are differentiable. Writing $X^{\prime}$
for the pixel-wise differentiation $\partial X/\partial I_{k,l}$, we have:

$\mathrm{FRC}^{\prime}(r)=\frac{A^{\prime}B-AB^{\prime}}{B^{2}}$ (9)

and

$B^{\prime}(r)=\sqrt{\frac{\sum_{S}|\mathcal{G}_{p,q}|^{2}}{\sum_{S}|\mathcal{F}_{p,q}|^{2}}}\,\sum_{S}\mathcal{F}_{p,q}\mathcal{F}^{\prime}_{p,q}$
(10)

and

$A^{\prime}(r)=\sum_{S}\mathcal{G}^{*}_{p,q}\,\mathcal{F}^{\prime}_{p,q}$ (11)

with

$\mathcal{F}^{\prime}_{p,q}=e^{-i2\pi(pk/M+ql/N)}\enspace.$ (12)

Here, we used that $\mathcal{G}$ is independent of $I$, that $\partial
I_{m,n}/\partial I_{k,l}=\delta_{m,k}\,\delta_{n,l}$, and the definition of
the Fourier transform Eq. (4). All of the these terms are well defined as long
as none of the images are empty, meaning that $\mathcal{L}_{\mathrm{FRC}}$ is
differentiable and hence mathematically valid as a loss function for training-
schemes that update weights and biases in neural networks via back-
propagation.

###  2.2 FRC limits

####  2.2.1 Large-frequency FRC approximation

Let us explore how the FRC behaves when one image $I$ is taken as ground truth
and the other is a copy with noise added $J=I+\eta$, with the expectation
values $\left<\eta\right>=0$ and
$\left<\eta_{m,n}\,\eta_{m^{\prime},n^{\prime}}\right>=\sigma_{\eta}^{2}\,\delta_{m,m^{\prime}}\,\delta_{n,n^{\prime}}$.
The linearity of the Fourier transform and the characteristics of the noise
directly gives

$\mathcal{G}_{p,q}=\mathcal{F}_{p,q}+\tilde{\eta}_{p,q}$ (13)

and the numerator of the FRC becomes

$\sum_{S}\mathcal{F}\,\mathcal{G}^{*}=\sum_{S}\mathcal{F}\,[\mathcal{F}+\tilde{\eta}]^{*}\simeq
n_{r}\left<|\mathcal{F}|^{2}\right>\simeq\sum_{S}|\mathcal{F}|^{2}$ (14)

where we approximated the sum over the annulus in frequency space with the
expectation value, which is zero for the Fourier transformed noise
$\left<\tilde{\eta}_{p,q}\right>=0$, and where $n_{r}$ is the number of
elements in S, i.e. number of pixels in frequency space satisfying
$p^{2}+q^{2}=r^{2}$. This result depends on $r$, but not on the strength of
the noise, and the approximation should be better the larger the area of the
annulus, i.e. for higher frequencies.

For the, squared, denominator we similarly find

$\sum_{S}|\mathcal{F}|^{2}\,\sum_{S}|\mathcal{G}|^{2}\simeq
n_{r}^{2}\left<|\mathcal{F}|^{2}\right>\left[\left<|\mathcal{F}|^{2}\right>+NM\,\sigma^{2}_{\eta}\right]\enspace.$
(15)

Forming the ratio of these two approximations and expanding to first order in
the noise $\sigma^{2}$, we get

$\displaystyle\mathrm{FRC}(I,I+\eta;r)$
$\displaystyle\simeq\frac{1}{\sqrt{1+NM\,\sigma_{\eta}^{2}/\left<|\mathcal{F}|^{2}\right>}}$
(16) $\displaystyle\simeq
1-\frac{1}{2}NM\,\sigma_{\eta}^{2}/\left<|\mathcal{F}|^{2}\right>$ (17)

which, as the noise goes to zero, approaches unity.

If, additionally, we assume that the power spectral density of the image
scales as one over frequency $\left<|\mathcal{F}|^{2}\right>\propto 1/r$, then
we see from Eq. (16) that the FRC will take on the characteristic form

$\mathrm{FRC}(I,I+\eta;r)\simeq\frac{1}{\sqrt{1+ar^{2}}}$ (18)

where $a$ is a factor that contains the frequency independent amplitudes of
the noise and the image. That is, the FRC decays smoothly from one to zero as
a function of frequency $r$, with an inflection point around $1/\sqrt{2a}$.

####  2.2.2 High noise, large frequency FRC approximation

For high noise, but still in the approximation of large frequencies, the FRC
in Eq. (16) trivially becomes

$\mathrm{FRC}(I,I+\eta;r)\simeq\frac{\left<|\mathcal{F}|^{2}\right>}{NM\,\sigma_{\eta}^{2}}\simeq\frac{\sum_{S}|\mathcal{F}|^{2}}{n_{r}NM\,\sigma_{\eta}^{2}}\enspace.$
(19)

That is, the FRC is inversely proportional to the strength of the noise in
this limit and approaches zero as the noise grows. Here, by large noise, we
mean $NM\sigma^{2}_{\eta}\gg\left<|\mathcal{F}|^{2}\right>$.

If, like above, we assume that the power of the signal scales as one over
frequency, we see that the FRC will simply exhibit that same behavior, as can
also be gleaned from Eq. (16) in the limit of large noise:

$\mathrm{FRC}(I,I+\eta;r)\simeq\frac{1}{r\sqrt{a}}$ (20)

###  2.3 Mathematical invariances of the FRC

####  2.3.1 Invariance to image scaling

Scaling of the images by multiplicative factors $a_{1}>0$ and $a_{2}>0$ has no
effect on the FRC:

$\mathrm{FRC}(a_{1}I,a_{2}J;r)=\mathrm{FRC}(I,J;r)\enspace.$ (21)

This is seen by inspection of the definition of the FRC and by remembering the
linearity of the Fourier transform: The Fourier transformed images appears
with the same power in the numerator and denominator, so the factors $a_{1}$
and $a_{2}$ cancel out. If we choose a negative scaling factor, the sign of
the FRC flips.

####  2.3.2 Pseudo-invariance to image offsets

Adding constants $b_{1}$ and $b_{2}$ to an image only affects the value of the
FRC at zero frequency

$\displaystyle\mathrm{FRC}(b_{1}+I,b_{2}+J;r>0)$
$\displaystyle=\mathrm{FRC}(I,J;r>0)$ (22)
$\displaystyle\mathrm{FRC}(b_{1}+I,b_{2}+J;r=0)$
$\displaystyle\neq\mathrm{FRC}(I,J;r=0)$ (23)

This, again follows directly from the properties of the Fourier transform and
the definition of the FRC.

####  2.3.3 Invariance to image filtering

If an image is filtered in the Fourier domain by an $r$-dependent function
that is radially symmetric, real, and positive, the FRC doesn’t change. This
is easily seen, as such a filter would simply show up as a multiplicative,
$r$-dependent factor (a real and positive scalar), in both the numerator and
the denominator of the FRC, and thus cancel out. This instantly tells us, via
application of the convolution theorem, that a certain class of spatial
filters also will not change the FRC. Any spatial filter whose Fourier
transform is real, positive, and only depend on $r$ will leave the FRC
invariant. A classic example would be smoothing in the image-domain by
convolution with an isotropic 2D Gaussian function $g$ (the Fourier transform
of a Gaussian is a Gaussian), which will have no effect on the FRC

$\mathrm{FRC}(I,g\star J;r)=\mathrm{FRC}(I,J;r)\enspace,$ (24)

where $\star$ denotes convolution.

##  3 Results

###  3.1 FRC as an Image Quality Metric

When FRC is determined between a noisy/restored image and the ground truth,
the resulting curve provides information on how much the two images correlate
over the frequency spectrum, as depicted in Figure 2. The one-dimensional FRC
view is advantageous as one can assess the quality of the signal as a function
of frequency, a distinct advantage when comparing to scalar metrics. However,
the area under the curve can also be calculated for each FRC curve, producing
a scalar, $1-\mathcal{L}_{\mathrm{FRC}}$, that can be compared to the more
traditional scalar loss-measures ($\mathcal{L}_{1}$, $\mathcal{L}_{2}$, PSNR,
SSIM).

To provide an example of the metric in action, we compare several FRC curves
for noisy and denoised images in Figure 2. The FRC is calculated between each
noisy/denoised image and its corresponding pair image (ground truth, noisy)
for 50 test images in the Google Open Images (GOI) dataset v5 [14] and
averaged (see Supplementary Materials).

The red line in Figure 2 shows that the FRC between two noisy realizations of
the same signal has an overall low value, especially for higher frequencies,
following the decay described in Eq. (20). When comparing a ground truth (GT)
image and one of the noisy realisations we observe a higher FRC over all
frequencies. This is expected, since lower noise levels, or denoising, of one
of the images should increase the FRC (see section 2.2). The standard BM3D
algorithm [5] restores some of the signal from the noisy image and improves
the FRC curve. However, a simple Gaussian filter (with sigma 1) only scales
the mean power spectra, effectively dumping higher frequencies, but does not
affect the FRC curve, (brown dotted line, see also Eq. (24) ). On the other
hand, a U-net based N2N network, trained on 50,000 images from the GOI dataset
(see Supplementary Materials), is a better denoiser than BM3D, with
particularly good performance in the medium and high frequency range (orange
line). When the denoising model is trained on a smaller training dataset (1000
images from the GOI set) a decrease in the performance of the denoiser is
observed, as expected.

Figure 2: N2N model performs best, Gaussian filter has no effect. To assess
denoising performance, the FRC can be calculated between the denoised image
and the ground truth or the noisy image. Higher FRC values indicates better
restoration. Several denoising approaches are shown (N2N-GOI network vs. GT,
orange line; BM3D method vs. GT, blue line; Gaussian filter vs. GT, brown
dotted line; N2N-GOI1000 network vs. GT, grey dashed line) along with curves
showing FRC for noisy data (noisy vs. noisy image, red line; noisy vs. GT
image, green line). Each curve shows an average FRC for 50 natural test images
from the GOI set, pre-processed with a Hann window to suppress edge artifacts
in the Fourier signal. $f/N$ denotes frequency normalised by the Nyquist
frequency for the images.

###  3.2 Comparison of FRC with standard metrics across corruptions

To investigate how well $\mathcal{L}_{\mathrm{FRC}}$ captures distortions, in
comparison to more established metrics such as MSE and SSIM, we compare the
performance of these metrics using the KADID-10 dataset containing
artificially distorted images that have corresponding differential mean
opinion scores (DMOS). DMOS is a human perception image quality score (between
1 and 5), derived through the use of internet crowdsourcing, see [17]).
KADID-10 contains 5 distortion levels for each type of distortion. Here, we
considered a set of 4 distortion types on the full set of 81 images from the
KADID-10 dataset. For each image and distortion type, the three metrics
($1-\mathcal{L}_{\mathrm{FRC}}$, MSE and SSIM) were applied to obtain an image
quality estimation scalar, resulting in 5x3 estimations (five levels of
distortion, three methods to evaluate). For each method, the five estimations
were correlated with the DMOS by using Pearson’s correlation coefficient
(using all images in the dataset). Our results are summarized in Figure S1 and
Table 1.

The performance of $1-\mathcal{L}_{\mathrm{FRC}}$ is competitive (Gaussian and
impulse noise) or better (jitter and motion blur) than SSIM and overall better
than the MSE metric. Both the SSIM and $1-\mathcal{L}_{\mathrm{FRC}}$ metrics
are sensitive to the quality of high frequency signals in images, which is
also expressed in the DMOS, as discussed in [30]. In contrast, the MSE metric,
as shown in Figure 3, depends mostly on the low frequency characteristic of an
image.

Distortion |  $1-\mathbf{\mathcal{L}_{\mathrm{FRC}}}$ |  MSE |  SSIM
---|---|---|---
Metric |  |  |
Gaussian |  0.94 (0.01) |  0.93 (0.01) |  0.95 (0.01)
Impulse |  0.94 (0.01) |  0.93 (0.01) |  0.94 (0.01)
Jitter |  0.97 (0.01) |  0.89 (0.02) |  0.95 (0.01)
Motion blur |  0.96 (0.01) |  0.95 (0.01) |  0.94 (0.01)

Table 1: Performance comparison of image quality assessment models on 81
images from the KADID-10 dataset. The performance is measured by calculating
each metrics and correlating it to the differential mean opinion score, DMOS,
obtained from the dataset. Average Pearson’s correlation coefficients for
$\mathcal{L}_{\mathrm{FRC}}$, MSE and SSIM vs. DMOS (over all 81 images in the
data set) with the standard error are shown. The best performance, for each
type of distortion, is shown in bold.

###  3.3 FRC as a loss function in neural networks

We have now shown that the FRC can be used as a metric to assess frequency-
dependent signal quality in natural images, with a sensitivity comparable to
or super-seeding the more well-known SSIM metric. Next, we explore the
characteristics of $\mathcal{L}_{\mathrm{FRC}}$ as a loss function for
training denoising neural networks. We begin by analysing the FRC loss
function dependency on spatial signal frequency, followed by experiments
measuring denoising performance across different noise corruptions. We compare
the results to the standard $\mathcal{L}_{2}$ (MSE) and, where relevant, the
$\mathrm{L_{1}}$ loss, $\mathcal{L}_{1}$.

####  3.3.1 FRC loss dependency on signal spatial frequency

To understand how the different losses restore information as a function of
frequency we used low-pass filtering for each of the 50 images in the test
dataset. In Fourier space, a range of cutoffs between zero and the Nyquist
frequency were applied to remove signal above a given frequency threshold.
Afterwards, images were inverse Fourier transformed, and the three loss
functions $\mathcal{L}_{1}$, $\mathcal{L}_{2}$, and
$\mathcal{L}_{\mathrm{FRC}}$ were calculated relative to the ground truth
images. After processing all available frequencies, the loss curves were
normalised, averaged for the full data-set, and shown in Figure 3. We observe
that almost all of the change in $\mathrm{L_{2}}$ happens in a narrow
frequency range close to zero, indicating a strong sensitivity to low spatial
frequencies or, reversely, a low sensitivity to high-frequency signals. This
may not be an issue for some applications, since most of the signal strength
is contained in the low frequencies in natural images; for scientific images
this is not universally the case though.. In contrast to this behavior
$\mathcal{L}_{\mathrm{FRC}}$ depends equally strongly on all frequencies as
shown by its linear response to cut-off frequency. The $\mathrm{L_{1}}$-loss
behaves similarly to $\mathcal{L}_{2}$, with slightly higher sensitivity to
the high frequency features. These result suggests that a network with the
$\mathrm{L_{2}}$-loss might be more difficult to train on high frequency
signal, when compared to models using $\mathrm{L_{1}}$ or
$\mathcal{L}_{\mathrm{FRC}}$.

Figure 3: $\mathcal{L}_{2}$ has weak sensitivity to image details. The plot
shows dependency of $\mathcal{L}_{1}$, $\mathcal{L}_{2}$, and
$\mathcal{L}_{\mathrm{FRC}}$ to the signal from natural images as function of
low-pass frequency. Iteratively, over the frequency from 1 up to Nyquist, a
cutoff in Fourier space was applied to remove signal above a given frequency
threshold. For each resulting low-pass filtered image $\mathcal{L}_{1}$,
$\mathcal{L}_{2}$, and $\mathcal{L}_{\mathrm{FRC}}$ were calculated relative
to the ground truth image. Averages over 50 test GOI images are plotted.
Before averaging, each image-loss curve was normalized. $f/N$ denotes
frequency normalised by the Nyquist frequency for the images.

####  3.3.2 FRC loss and noise distributions

In the theory section 2.1 we showed that $\mathcal{L}_{\mathrm{FRC}}$ is
differentiable and can be used as a loss-function in neural network model
training. Here, we test its performance in image denoising. We compare
denoising with $\mathcal{L}_{\mathrm{FRC}}$ against $\mathcal{L}_{1}$ and
$\mathcal{L}_{2}$ based denoising for two artificial corruptions, Gaussian and
log-normal noise, as well as experimental noise in single particle cryo-
electron microscopy images.

Since minimising $\mathcal{L}_{2}$ corresponds to maximising a model log-
likelihood when denoising data with a Gaussian noise, $\mathcal{L}_{2}$ should
give optimal results for such dataset. Similarly, $\mathcal{L}_{1}$ should be
optimal for denoising images with log-normal noise. The distribution of noise
in electron microscopy images can be approximated, but in principle it is not
known, making a choice of a loss function more arbitrary. The properties of
the applied noise distributions are given in the Supplementary Materials.

Here, we test the hypothesis that $\mathcal{L}_{\mathrm{FRC}}$ will provide
comparable results to $\mathcal{L}_{2}$ for Gaussian noise, to
$\mathcal{L}_{1}$ for log-normal noise, and possibly high quality results for
the cryo-EM data images. In Figure 4 we see that the FRC-loss allows
significantly faster convergence of network parameters, for all three data
sets. Notably, SSIM values for Gaussian noise after $2^{5}$ training steps
with $\mathcal{L}_{\mathrm{FRC}}$ are comparable to SSIM values for
$\mathcal{L}_{2}$ after $2^{10}$ training steps (top row, right column in
Figure 4). This is likely due to stronger gradients for high frequency
features for this loss. We also observe that $\mathrm{L_{1}}$-loss for the
log-normal noise data set converges faster than $\mathrm{L_{2}}$-loss, but
slower than $\mathcal{L}_{\mathrm{FRC}}$, which is consistent with the results
shown in Figure 3.

Eventually, all three loss functions converge to the same level: Final results
from long training ($2^{19}$ steps $\simeq 200$ epochs) are similar for all
three loss functions and the three metrics we used
($\mathcal{L}_{\mathrm{FRC}}$, MSE, SSIM). In [16] authors show that for
impulse noise corruption, differences between $\mathcal{L}_{1}$ and
$\mathcal{L}_{2}$ are small and only visible for very high noise rates.

In the case of experimental cryo-EM images, $\mathcal{L}_{\mathrm{FRC}}$ loss
outperforms $\mathcal{L}_{2}$ in the FRC metrics. For this data set, which has
only about 10,000 image pairs used during training, we see very high noise
levels which affect the absolute FRC, MSE, and SSIM levels and obscure MSE and
SSIM values. In the FRC plots we observe effects of over-fitting which result
in the decay of the metric (calculated on 200 test set images, bottom row in
Figure 4). Interestingly, the over-fitting happens faster for the
$\mathcal{L}_{\mathrm{FRC}}$. We note that $\mathcal{L}_{\mathrm{FRC}}$ is
computationally more expensive per epoch; with the current implementation,
training with the same number of epochs is about 1.5 times longer compared to
$\mathcal{L}_{2}$, but the gains due to the loss properties (much fewer epochs
needed to converge) are much larger. We also note that
$\mathcal{L}_{\mathrm{FRC}}$ does not optimise the absolute values of the
image power-spectra, which can possibly drift during training.

Figure 4: Comparison of loss function performance in N2N denoising network
trained for two artificial corruptions and a real-world noise. Top row:
Gaussian noise (GOI data set), middle row: log-normal noise (GOI data set),
bottom row: electron microscopy single particle data.
$\mathcal{L}_{\mathrm{FRC}}$ (blue line) was compared to the statistically
best loss function for each corruption ($\mathcal{L}_{2}$, green line, for
Gaussian noise, and $\mathcal{L}_{1}$, orange line, for log-normal noise). For
electron microscopy images, results for $\mathcal{L}_{\mathrm{FRC}}$ and
$\mathcal{L}_{2}$ are plotted. $\mathcal{L}_{\mathrm{FRC}}$, MSE and SSIM
metrics averages for 50 (GOI) or 200 (cryoEM) test images, for the
corresponding data sets, are shown.

###  3.4 Denoising and signal power distribution

Previous studies have observed that denoising networks have an inherent
spectral bias [21, 10], that skews their learning towards low complexity
solutions. Practically, this manifests as a more robust learning in the lower
frequencies. Related work by [25] reports a strong denoising ability on the
low-frequencies when training a convolutional auto-encoder on a single noisy
image and regularizing by early stopping. Employing FRC analysis we also
observe that denoising low frequency is faster than denoising high frequency
signal for both $\mathcal{L}_{2}$ and $\mathcal{L}_{\mathrm{FRC}}$ (see Figure
S2). In general, what these works ([21, 10]) emphasize is that an over-
parameterized network, where the network has sufficiently many parameters to
represent an arbitrary image (including noise) perfectly, fits the signal of a
natural image faster than noise. Furthermore, the very network itself has an
inherent bias toward lower frequencies, meaning the signal restoration at
lower frequencies is significantly better than mid to high range frequencies.
Several components of neural networks have been attributed to be the cause of
this spectral bias, for instance the optimization algorithm itself, ReLu
functions [25, 20] and pooling layers. Here, we investigate this spectral bias
by denoising natural images with an altered power spectrum where all
frequencies have equal mean power; we refer to these images as ”power-
normalised”. We are interested in whether or not the spectral bias of neural
networks is a matter of inherent preference for low frequencies or if it is
rather just a coincidental correlation caused by the location of the largest
signal power, which for natural images happens at low frequencies [22]. For
this, we power-normalised 1000 GOI images, as explained in the Supplementary
material and shown in Figure S3. The set of power normalised and original
images (with the added Gaussian noise) were used to train two N2N networks
with $\mathcal{L}_{2}$ loss. We find that the signal is recovered much more
uniformly as a function of frequency for the network trained on power-
normalised images (Figure S4A). This suggests that spectral bias is in fact
not a bias as much in the frequency aspect, as it is for the location of
signal power. As a consequence, neural networks learn better to denoise
stronger signals, i.e./ the low frequency features. However, when the signal
is normalised, denoising efficiency ceases to be strongly dependent on
frequency, as can be seen from the FRC analysis.

##  4 Discussion and conclusions

Here, we explore denoising through the lens of the Fourier Ring Correlation
and the associated $\mathcal{L}_{\mathrm{FRC}}$ loss/metric function. First,
we establish the $\mathcal{L}_{\mathrm{FRC}}$ to be an effective metric, with
sensitivity comparable to and exceeding the more established SSIM, while
offering the advantage of qualitatively assessing the signal quality as a
function of frequency. Further, we compare and contrast several denoising
methods, including U-nets and the BM3D method, and their ability to denoise
high-frequency signals in images. We then explore the extent to which
$\mathcal{L}_{\mathrm{FRC}}$ may be used more directly in denoising—as a loss
function for neural networks trained by back-propagation—by considering three
different types of noise corruptions and comparing to the statistically
optimal metric for each case. We conclude that all loss functions ultimately
converge to similar denoising level, but that the convergence rate for
$\mathcal{L}_{\mathrm{FRC}}$ is markedly faster than for $\mathcal{L}_{1}$ and
$\mathcal{L}_{2}$, albeit computationally more expensive per epoch. In
parallel, we provide some mathematical properties of the Fourier Ring
Correlation function by deriving its limits at low and high noise and by
proving that $\mathcal{L}_{\mathrm{FRC}}$ is analytically differentiable, thus
qualifying as a valid loss function.

Finally, we use the FRC to characterise some peculiarities of neural network
denoisers: We confirm the spectral bias mentioned in a multitude of prior
studies, but find it to be a circumstantial effect, caused by the majority of
the signal strength being found at low frequencies. That is, the frequency-
dependent denoising power of a network seems to be a knock-on effect of the
spectral distribution of the signal and not inherent to the network itself. In
the Supplementary Material we explore some potential FRC limitations due to
denoising bias.

## References

  * [1] Niccolò Banterle, Khanh Huy Bui, Edward A. Lemke, and Martin Beck.  Fourier ring correlation as a resolution criterion for super-resolution microscopy.  Journal of Structural Biology, 183(3):363–367, 2013.
  * [2] Joshua Batson and Loic Royer.  Noise2self: Blind denoising by self-supervision.  arXiv preprint arXiv:1901.11365, 2019.
  * [3] Andreas Berberich, Andreas Kurz, Sebastian Reinhard, Torsten Johann Paul, Paul Ray Burd, Markus Sauer, and Philip Kollmannsberger.  Fourier ring correlation and anisotropic kernel density estimation improve deep learning based smlm reconstruction of microtubules.  Frontiers in Bioinformatics, 1:55, 2021.
  * [4] Siân Culley, David Albrecht, Caron Jacobs, Pedro Matos Pereira, Christophe Leterrier, Jason Mercer, and Ricardo Henriques.  Quantitative mapping and minimization of super-resolution optical imaging artifacts.  Nature Methods, pages 1–10, Feb. 2018.
  * [5] Kostadin Dabov, Alessandro Foi, Vladimir Katkovnik, and Karen Egiazarian.  Image denoising by sparse 3-d transform-domain collaborative filtering.  IEEE Transactions on image processing, 16(8):2080–2095, 2007.
  * [6] Kostadin Dabov, Alessandro Foi, Vladimir Katkovnik, and Karen Egiazarian.  Bm3d image denoising with shape-adaptive principal component analysis.  In SPARS’09-Signal Processing with Adaptive Sparse Structured Representations, 2009.
  * [7] A Descloux, K S Grußmayer, and A Radenovic.  Parameter-free image resolution estimation based on decorrelation analysis.  Nature Methods, pages 1–11, Aug. 2019.
  * [8] Ahmet M Eskicioglu and Paul S Fisher.  Image quality measures and their performance.  IEEE Transactions on communications, 43(12):2959–2965, 1995.
  * [9] George Harauz and Marin van Heel.  Exact filters for general geometry three dimensional reconstruction.  Optik (Stuttgart), 73(4):146–156, 1986.
  * [10] Reinhard Heckel and Mahdi Soltanolkotabi.  Denoising and regularization via exploiting the structural bias of convolutional generators.  arXiv preprint arXiv:1910.14634, 2019.
  * [11] Sami Koho, Giorgio Tortarolo, Marco Castello, Takahiro Deguchi, Alberto Diaspro, and Giuseppe Vicidomini.  Fourier ring correlation simplifies image restoration in fluorescence microscopy.  Nature communications, 10(1):1–9, 2019.
  * [12] Alexander Krull, Tim-Oliver Buchholz, and Florian Jug.  Noise2void-learning denoising from single noisy images.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2129–2137, 2019.
  * [13] Alexander Krull, Tomas Vicar, and Florian Jug.  Probabilistic noise2void: Unsupervised content-aware denoising.  arXiv preprint arXiv:1906.00651, 2019.
  * [14] Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Alexander Kolesnikov, Tom Duerig, and Vittorio Ferrari.  The open images dataset v4: Unified image classification, object detection, and visual relationship detection at scale.  IJCV, 2020.
  * [15] Samuli Laine, Tero Karras, Jaakko Lehtinen, and Timo Aila.  High-quality self-supervised deep image denoising.  In Advances in Neural Information Processing Systems, pages 6968–6978, 2019.
  * [16] Jaakko Lehtinen, Jacob Munkberg, Jon Hasselgren, Samuli Laine, Tero Karras, Miika Aittala, and Timo Aila.  Noise2noise: Learning image restoration without clean data.  arXiv preprint arXiv:1803.04189, 2018.
  * [17] Hanhe Lin, Vlad Hosu, and Dietmar Saupe.  Kadid-10k: A large-scale artificially distorted iqa database.  In 2019 Tenth International Conference on Quality of Multimedia Experience (QoMEX), pages 1–3. IEEE, 2019.
  * [18] Mangal Prakash, Alexander Krull, and Florian Jug.  Fully unsupervised diversity denoising with convolutional variational autoencoders.  In International Conference on Learning Representations, 2021.
  * [19] Mangal Prakash, Manan Lalit, Pavel Tomancak, Alexander Krul, and Florian Jug.  Fully unsupervised probabilistic noise2void.  In 2020 IEEE 17th International Symposium on Biomedical Imaging (ISBI), pages 154–158. IEEE, 2020.
  * [20] Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville.  On the spectral bias of neural networks.  In International Conference on Machine Learning, pages 5301–5310. PMLR, 2019.
  * [21] Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred A Hamprecht, Yoshua Bengio, and Aaron Courville.  On the spectral bias of neural networks.  arXiv preprint arXiv:1806.08734, 2018.
  * [22] Daniel L Ruderman and William Bialek.  Statistics of natural images: Scaling in the woods.  Physical review letters, 73(6):814, 1994.
  * [23] W O SAXTON and W BAUMEISTER.  The Correlation Averaging of a Regularly Arranged Bacterial-Cell Envelope Protein.  Journal of Microscopy, 127(AUG):127–138, 1982.
  * [24] Chunwei Tian, Yong Xu, and Wangmeng Zuo.  Image denoising using deep cnn with batch renormalization.  Neural Networks, 121:461–473, 2020.
  * [25] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky.  Deep image prior.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9446–9454, 2018.
  * [26] Marin Van Heel.  Similarity measures between images.  Ultramicroscopy, 21(1):95–100, 1987.
  * [27] M Van Heel, W Keegstra, W Schutter, and EJF Van Bruggen.  Arthropod hemocyanin structures studied by image analysis.  Life Chem. Rep. Suppl, 1:69–73, 1982.
  * [28] Marin Van Heel and Michael Schatz.  Fourier shell correlation threshold criteria.  Journal of structural biology, 151(3):250–262, 2005.
  * [29] Zhou Wang, Alan C Bovik, Hamid R Sheikh, and Eero P Simoncelli.  Image quality assessment: from error visibility to structural similarity.  IEEE transactions on image processing, 13(4):600–612, 2004.
  * [30] Zhou Wang, Eero P Simoncelli, and Alan C Bovik.  Multiscale structural similarity for image quality assessment.  In The Thrity-Seventh Asilomar Conference on Signals, Systems & Computers, 2003, volume 2, pages 1398–1402. Ieee, 2003.
  * [31] Martin Weigert, Uwe Schmidt, Tobias Boothe, Andreas Müller, Alexandr Dibrov, Akanksha Jain, Benjamin Wilhelm, Deborah Schmidt, Coleman Broaddus, Siân Culley, et al.  Content-aware image restoration: pushing the limits of fluorescence microscopy.  Nature methods, 15(12):1090–1097, 2018.
  * [32] Dong Yang and J. Sun.  Bm3d-net: A convolutional neural network for transform-domain collaborative filtering.  IEEE Signal Processing Letters, 25:55–59, 2018.
  * [33] Kai Zhang, Wangmeng Zuo, Yunjin Chen, Deyu Meng, and Lei Zhang.  Beyond a gaussian denoiser: Residual learning of deep cnn for image denoising.  IEEE Transactions on Image Processing, 26(7):3142–3155, 2017.
  * [34] Kai Zhang, Wangmeng Zuo, and Lei Zhang.  Ffdnet: Toward a fast and flexible solution for cnn-based image denoising.  IEEE Transactions on Image Processing, 27(9):4608–4622, 2018.
  * [35] Hang Zhao, Orazio Gallo, Iuri Frosio, and Jan Kautz.  Loss functions for neural networks for image processing.  arXiv preprint arXiv:1511.08861, 2015.


# Damage Estimation and Localization from Sparse Aerial Imagery ††thanks:
DISTRIBUTION STATEMENT A. Approved for public release. Distribution is
unlimited. This material is based upon work supported by the United States Air
Force under Air Force Contract No. FA8702-15-D-0001. Any opinions, findings,
conclusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of the United States Air
Force. © 2021 Massachusetts Institute of Technology. Delivered to the U.S.
Government with Unlimited Rights, as defined in DFARS Part 252.227-7013 or
7014 (Feb 2014). Notwithstanding any copyright notice, U.S. Government rights
in this work are defined by DFARS 252.227-7013 or DFARS 252.227-7014 as
detailed above. Use of this work other than as specifically authorized by the
U.S. Government may violate any copyrights that exist in this work. This work
was also made possible in part due to funding from NSF D-ISN project award #
2039771.

René García Franceschini
Institute for Data, Systems and Society
Massachusetts Institute of Technology
Cambridge, MA
<EMAIL_ADDRESS>&Jeffrey Liu
MIT Lincoln Laboratory
Lexington, MA
<EMAIL_ADDRESS>&Saurabh Amin
Dept. of Civil and Environmental Engineering
Massachusetts Institute of Technology
Cambridge, MA
<EMAIL_ADDRESS>
###### Abstract

Aerial images provide important situational awareness for responding to
natural disasters such as hurricanes. They are well-suited for providing
information for damage estimation and localization (DEL); i.e., characterizing
the type and spatial extent of damage following a disaster. Despite recent
advances in sensing and unmanned aerial systems technology, much of post-
disaster aerial imagery is still taken by handheld DSLR cameras from small,
manned, fixed-wing aircraft. However, these handheld cameras lack IMU
information, and images are taken opportunistically post-event by operators.
As such, DEL from such imagery is still a highly manual and time-consuming
process. We propose an approach to both detect damage in aerial images and
localize it in world coordinates. The approach is based on using structure
from motion to relate image coordinates to world coordinates via a projective
transformation, using class activation mapping to detect the extent of damage
in an image, and applying the projective transformation to localize damage in
world coordinates. We evaluate the performance of our approach on post-event
data from the 2016 Louisiana floods, and find that our approach achieves a
precision of 88%. Given this high precision using limited data, we argue that
this approach is currently viable for fast and effective DEL from handheld
aerial imagery for disaster response.

##  1 Application Context

Natural disasters, such as hurricanes and floods, can cause major loss of life
and property; the intensity, scope, and the frequency of such disasters may be
further exacerbated by global climate change [1]. Timely information about the
distribution and nature of damage following a disaster can help provide
important context and information for emergency managers’ decision-making [2].
Increasingly, satellite and aerial imagery are being incorporated into post-
disaster needs assessment [3]. However, while techniques exist for extracting
information from orthorectified satellite and aerial imagery [4, 5, 6, 7, 8],
methods for more general aerial imagery (such as oblique imagery from handheld
cameras) have received far less attention. This is a critical limitation
because post-disaster aerial imagery taken from handheld DSLR cameras from
small, manned, fixed-wing aircraft remains popular due to the relatively low
cost, high availability, conformity with existing regulations, and existing
training programs associated with the practice [9, 10]. These handheld cameras
lack IMU information, and images are taken opportunistically post-event by
human operators, resulting in sparsely-sampled images taken at oblique angles.
In this paper, we pose the question: how can we use aerial imagery from an
arbitrary camera setup in order to rapidly and effectively aid in post-
disaster situational awareness?

We focus on a specific component of post-disaster needs assessment, which we
refer to as Damage Estimation and Localization (DEL). We broadly define damage
as an identifiable destruction of an infrastructure component or utility
resulting from a specific event (in our case, a natural disaster). We then
define estimation as the detection of an instance of damage in an image.
Finally, localization is the act of assigning world coordinates to the
estimated instance of damage. Our main contribution is a practically
implementable approach that uses sparse, oblique aerial disaster imagery from
handheld cameras to carry out DEL. To our knowledge, our approach is the only
one that does estimation without relying on training data that includes
bounding boxes or segmented images; and localization without inertial
measurement unit (IMU) information or a known geotransform. We show that this
method applied to flooding DEL achieves a precision of 88% when compared
against official estimates from the 2016 Louisiana floods. We believe our
approach provides emergency managers the means to do fast and effective DEL
using existing equipment.

The approach consists of two stages: a pre-disaster and a post-disaster stage.
In the pre-disaster stage, a neural network is trained to classify damage
within low altitude disaster imagery. The post-disaster stage is comprised of
two parallel ’pipelines’, whose outputs are combined at the end. The first
pipeline takes a collection of images from an area of interest and
reconstructs the scene using structure from motion to obtain a projective
transformation that relates image coordinates to world coordinates. The second
pipeline takes individual images from the area of interest and produces
polygons that cover the extent of the damage that is detected using class
activation mapping. The projective transformation is then applied to the
damage polygons to produce an estimate of damage locations in world
coordinates. Appendix A illustrates this approach.

Existing work in this area has focused primarily on nadir (top-down) or
orthorectified imagery. For georeferencing, common approaches use visual
feature-based methods such as SIFT to register satellite or nadir drone
imagery to other known georeferenced images [11, 12, 13, 14]. However, methods
such as SIFT have been shown to perform poorly under extreme changes in
perspective and sensor specifications [13, 15]. Deep learning approaches using
Siamese neural networks have been proposed for georeferencing aerial images
[16, 17, 15, 18]; however, these approaches do not recover the orientation
information necessary to project the oblique images to the world coordinates.
Indeed, most available literature on registering oblique imagery relies on
some variant of structure from motion or multiview stereo [19], which is the
approach we take for georeferencing. For detecting damage, various deep
learning approaches have achieved high accuracy in object detection challenges
such as xView2 [4, 5, 6]. Previous work has also attempted to overcome lack of
training data in either satellite or aerial images via transfer learning from
satellite to aerial or vice versa [20, 21, 22]. Once again, these approaches
were only applied to orthorectified imagery. Given the lack of tools and
datasets developed for detecting damage within oblique aerial photos, we
pursue a weakly supervised approach to detecting damage using class activation
mapping.

##  2 Methods

###  2.1 Low Altitude Disaster Imagery dataset

The data used in this paper comes from the Low Altitude Disaster Imagery
(LADI) dataset [23]. LADI is a publicly available dataset consisting of images
taken by the United States Civil Air Patrol (CAP) in the aftermath of natural
disasters, and annotated by crowdsourced workers with hierarchical image-level
labels representing five broad categories: Damage, Environment,
Infrastructure, Vehicles, and Water. Within each category, there are a number
of more specific annotation labels. We focus on the flooding/water damage
label within in the “Damage" category.

###  2.2 Damage estimation within an image

This section describes our damage estimation pipeline. We train an image
classifier to detect damage, and use the class activation map from the
classifier to estimate the location of damage within images.

####  2.2.1 Classification with ResNet

To perform the image labeling task, we use a ResNet-50 backbone architecture
[24] pretrained on ImageNet [25] and fine tuned on the LADI dataset. ImageNet
weights are used due to their status the default pretrained weights for
popular implementations of ResNet-50 [26, 27]; additional work is necessary to
determine if performance could be improved by pretraining on an overhead
imagery dataset, such as xBD [4]. Images within the LADI dataset were shown to
multiple workers per category; we considered an image a positive example if at
least two workers marked it as such. Appendix B provides further details on
how we constructed the training labels from worker responses. We split the
dataset 80%/10%/10% for the training, validation and testing sets,
respectively. The ResNet achieves a performance of 77% accuracy, 65%
precision, and 79% recall on the validation set; see Appendix B for more
details.

(a) Original image

(b) CAM mask

(c) Polygon tracing

Figure 1: Stages of our polygon tracing approach.

####  2.2.2 Class activation mapping and polygon tracing

After training, we utilize the class activation mapping (CAM) approach from
Zhou et al. [28] to localize the extent of the detected class within the
image. CAM is a technique for weakly-supervised object detection, which
leverages the average pooling layer at the end of the ResNet architecture to
detect areas within an image that are important for classifying a particular
class. We threshold the pooling layer (see Appendix C to generate a mask, and
convert the mask into a set of polygons using [29]. Fig. 1 shows different
stages of this procedure.

###  2.3 Damage localization

This section describes the localization pipeline: estimating the projective
transformation relating image and world coordinates using SfM, and applying it
to transform the flooding polygons.

####  2.3.1 Reconstruction using structure from motion

Structure from motion is a technique that, using images from a camera moving
through an environment, can produce a point cloud of the environment [30]. By
taking advantage of the GPS tags from the image metadata or from outside
sensors, structure from motion has been used to create inexpensive,
georeferenced elevation models from drone and aircraft imagery [31]. We use
this technique as an intermediate step to obtaining the projective
transformation that relates image coordinates to world coordinates. We base
our implementation off the well-known OpenSfM library, an open source library
for structure from motion [32].

Since fixed wing aircraft tend to fly in a straight line, and have a
relatively large turn radius compared to rotary-wing aircraft, sequential
images collected from fixed-wing platforms tend to be approximately collinear.
Thus, some reconstructions have an additional degree of freedom from rotating
about the line that goes through the GPS coordinates. We address this by
separately estimating the direction of the up-vector (the vector opposite the
direction of gravity) and enforcing it in the reconstruction. Previous
implementations in urban environments have suggested estimating vanishing
points to estimate the up-vector [33]. This may be difficult if there are few
straight features (such as roads), which is common in rural areas.

To estimate the up-vector, we assume the ground is approximately flat. We
first fit a plane through the reconstructed features using RANSAC [34]. There
is a pair of possible antiparallel unit normal vectors to this plane, one of
which is the up-vector. Because of the aerial nature of the data, the location
of the images must be above the ground plane. Therefore, we choose the vector
that has a positive projection onto the image location in East, North Up (ENU)
coordinates and denote it $v_{up}$. Finally, we rotate the reconstruction so
that $v_{up}$ indeed points upwards. Specifically, we rotate it by $R_{z}$
such that $R_{z}v_{up}=\hat{z}$ when it is initialized, and the up-vector is
enforced during bundle adjustment. In areas with significant variation in
local topology, a digital elevation model (DEM) can be used to estimate the
ground plane. We had initially incorporated a digital elevation model (DEM).
However, since the region that we considered is relatively flat, there was no
difference in performance, and thus, we do not report the DEM results.

####  2.3.2 Image-to-world projective transformation

The final step in our georeferencing pipeline is estimating the transformation
from image coordinates to world coordinates, and applying it to the detected
damage polygons. As discussed previously, the images are of mostly flat
surfaces, and thus the coordinates can be related by a projective
transformation [30], and outliers can be filtered through RANSAC [34]. Of all
of the images that were reconstructed using OpenSfM, we retained those where
at least 20% of matches between image and world coordinates were inliers. Of
the retained images, we found that some images produced extremely large image
footprints (i.e., , the projection of the image edges onto the ground). We
identified that these photos were those that were so oblique that the horizon
was visible. Because such images require more complex transformations, we
eliminated them from our analysis. We considered two heuristic criteria for
eliminating such images. First, we eliminated images whose total area were
greater than some value $\gamma_{1}$. Second, we did not consider images where
the ratio of the longest side to the shortest side of the minimum area
rectangle that covered the entire footprint was greater than $\gamma_{2}$. We
report our results for a variety of $\gamma_{1}$ and $\gamma_{2}$ parameters
to illustrate the effectiveness of our approach.

##  3 Evaluation and Results

Figure 2: Map of East Baton Rouge parish and image GPS tags.

In this section, we evaluate the performance of our approach at DEL using
images from the 2016 Louisiana floods. Figure 2 shows the administrative
boundary of the East Baton Rouge parish in Louisiana, the parish’s estimated
flood inundation area [35], and the coordinates of all CAP image with GPS
locations within 5 km of the administrative boundary. In total, the flooding
event covered 536 km2 (44% of the total area of the parish). Our analysis
includes 1615 CAP images that were taken in August 2016 immediately after the
flooding event. Of these CAP images that were considered, 809 were
successfully reconstructed by OpenSfM. At the same time, 996 of the images
were identified as having flooding. Finally, 559 images both completed the
georeferencing pipeline and were identified as flooding. Additional images
were then filtered based on the criteria described in Section 2.3.2.

We evaluated three different methods of estimating flooding. First, we use the
GPS tag of these images as a baseline, where we calculate the precision as the
proportion of the flood images that lie in the FEMA estimates. Second, we
estimate the flooding using the entire footprints of images classified as
containing “flooding/water" (SfM + binary classification). Finally, we
consider our approach of both (SfM + CAM) as the flood estimate. For the SfM +
binary classification and SfM + CAM approaches, we compute precision as the
fraction of the computed flooding polygons which overlap with the official
FEMA estimates. We only consider the flooding within the East Baton Rouge
administrative boundary, since we do not have data on flood extent outside of
the boundary.

(a) GPS tags (Prec: 52%)

(b) Image footprints (Prec: 80%)

(c) Our approach (Prec: 88%)

Figure 3: Flooding estimates and precision values using: (a) GPS tags, (b)
image footprints (SfM + binary classification), and (c) our approach (SfM +
CAM).

Figure 3 shows the different flooding estimates overlaid against the official
estimates, as well as the precision values of each method. Note that the
precision we report is compared against the flooding extent estimates, and not
with ground truth mask of the images (which are not available in the dataset).
The reported precision includes both the contributions of CAM and SfM. These
estimates were made with $\gamma_{1}=4$ and $\gamma_{2}=5$ km2, so that
ultimately 243 images were used. These results show a clear improvement going
from using the image GPS locations to using the georeferenced footprint. This
suggests that using the GPS of the image location is insufficient, as a large
number of images containing flooding were taken over areas that were not
flooded, and vice versa. Furthermore, we see that our approach (SfM + CAM)
further improves the precision compared to using the full image footprint.
Especially at the edges of the flooding extent, our method provides a more
precise outline of the official estimates than using the full image
footprints. Appendix E provides a closeup view.

SfM + binary classification |  |  $\gamma_{2}$ (km2)
---|---|---
|  | 1 | 2.5 | 5 | 10
| 2 | 86 | 85 | 85 | 87
| 3 | 85 | 84 | 85 | 86
| 4 | 85 | 84 | 80 | 72
$\gamma_{1}$ (unitless) | 5 | 85 | 84 | 77 | 68

SfM + CAM |  |  $\gamma_{2}$ (km2)
---|---|---
|  | 1 | 2.5 | 5 | 10
| 2 | 90 | 89 | 89 | 89
| 3 | 90 | 88 | 87 | 87
| 4 | 90 | 88 | 88 | 87
$\gamma_{1}$ (unitless) | 5 | 90 | 88 | 87 | 87

Table 1: Precision for both approaches in percent for various values of
$\gamma_{1}$ and $\gamma_{2}$.

To characterize the improvement that our approach (SfM+CAM) provides over
using the entire image footprints (SfM + binary classification), we compute in
Table 1 the precision for various combinations of $\gamma_{1}$ and
$\gamma_{2}$. We see that for all chosen combinations, the SfM+CAM approach is
more precise. In addition, the precision of the footprint approach degrades
from 86% to 68% as the values of $\gamma_{1}$ and $\gamma_{2}$ increase, while
the performance of our approach only decreases from 90% to 87%. Thus, our
approach is more robust to the choices of these parameters, and allows us to
incorporate more of the highly-oblique images that would otherwise affect
performance in the footprint approach.

##  4 Discussion and Conclusion

In this paper, we addressed the problem of Damage Estimation and Localization
(DEL) using aerial images taken from handheld cameras in small, manned, fixed-
wing aircraft. While this mode of collecting imagery is cost-efficient and
compliant with existing regulations, such images are often highly oblique,
sparsely and irregularly sampled, and lack IMU information. We proposed an
approach to performing DEL from such images by combining SfM and CAM to
georeference images and detect damage within them. When compared against
official flooding estimates from the 2016 Louisiana floods, our approach
achieved a precision of 88%, which outperforms the naive approaches of using
the image GPS locations or image footprint. Our approach faces some
limitations: extremely oblique images which contain the horizon are unable to
be georeferenced using projective transformations, and images that do not
overlap with other images cannot be processed using SfM. Nevertheless, our
approach can quickly generate an estimate of damage distribution from aerial
imagery that is already being collected with existing equipment.

## References

  * [1] M. K. V. Aalst, “The impacts of climate change on the risk of natural disasters,” _Disasters_ , vol. 30, no. 1, pp. 5–18, 2006, _eprint: https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-9523.2006.00303.x. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-9523.2006.00303.x
  * [2] T. Cova, _GIS in Emergency Management_ , 12 1999, pp. 845–858.
  * [3] M. Technologies, “Digitalglobe’s rapid response to the devastating fort mcmurray…,” May 2016. [Online]. Available: https://blog.maxar.com/open-data-program/2016/digitalglobes-rapid-response-to-the-devastating-fort-mcmurray-wildfire
  * [4] R. Gupta, R. Hosfelt, S. Sajeev, N. Patel, B. Goodman, J. Doshi, E. Heim, H. Choset, and M. Gaston, “xbd: A dataset for assessing building damage from satellite imagery,” _arXiv preprint arXiv:1911.09296_ , 2019.
  * [5] S. A. Chen, A. Escay, C. Haberland, T. Schneider, V. Staneva, and Y. Choe, “Benchmark dataset for automatic damaged building detection from post-hurricane remotely sensed imagery,” _arXiv preprint arXiv:1812.05581_ , 2018.
  * [6] M. Rahnemoonfar, T. Chowdhury, A. Sarkar, D. Varshney, M. Yari, and R. Murphy, “Floodnet: A high resolution aerial imagery dataset for post flood scene understanding,” _arXiv preprint arXiv:2012.02951_ , 2020.
  * [7] R. Gupta and M. Shah, “Rescuenet: Joint building segmentation and damage assessment from satellite imagery,” _arXiv preprint arXiv:2004.07312_ , 2020\.
  * [8] A. J. Cooner, Y. Shao, and J. B. Campbell, “Detection of urban damage using remote sensing and machine learning algorithms: Revisiting the 2010 haiti earthquake,” _Remote Sensing_ , vol. 8, no. 10, p. 868, 2016.
  * [9] Department of Homeland Security, “DHS/FEMA/PIA-055 FEMA Response Use of Unmanned Aircraft System (UAS) Derived Imagery,” Tech. Rep., May 2020. [Online]. Available: https://www.dhs.gov/publication/dhsfemapia-055-fema-response-use-unmanned-aircraft-system-uas-derived-imagery
  * [10] Civil Air Patrol, “CAPabilities Briefing,” Apr. 2020. [Online]. Available: https://www.gocivilairpatrol.com/programs/emergency-services/capabilities-handbooks-briefing
  * [11] D. G. Lowe, “Object recognition from local scale-invariant features,” in _Proceedings of the seventh IEEE international conference on computer vision_ , vol. 2. Ieee, 1999, pp. 1150–1157.
  * [12] J. Oh, C. K. Toth, and D. A. Grejner-Brzezinska, “Automatic georeferencing of aerial images using stereo high-resolution satellite images,” _Photogrammetric Engineering & Remote Sensing_, vol. 77, no. 11, pp. 1157–1168, 2011.
  * [13] X. Zhuo, T. Koch, F. Kurz, F. Fraundorfer, and P. Reinartz, “Automatic uav image geo-registration by matching uav images to georeferenced image data,” _Remote Sensing_ , vol. 9, no. 4, p. 376, 2017.
  * [14] H. Goncalves, L. Corte-Real, and J. A. Goncalves, “Automatic image registration through image segmentation and sift,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 49, no. 7, p. 2589–2600, Jul 2011.
  * [15] A. Shetty and G. X. Gao, “Uav pose estimation using cross-view geolocalization with satellite imagery,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 1827–1833.
  * [16] Y. Tian, C. Chen, and M. Shah, “Cross-view image matching for geo-localization in urban environments,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 3608–3616.
  * [17] D.-K. Kim and M. R. Walter, “Satellite image-based localization via learned embeddings,” in _2017 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2017, pp. 2073–2080.
  * [18] L. Liu and H. Li, “Lending orientation to neural networks for cross-view geo-localization,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 5624–5633.
  * [19] S. Verykokou and C. Ioannidis, “Oblique aerial images: a review focusing on georeferencing procedures,” _International Journal of Remote Sensing_ , vol. 39, no. 11, pp. 3452–3496, 2018.
  * [20] L. Cao, C. Wang, and J. Li, “Vehicle detection from highway satellite images via transfer learning,” _Information sciences_ , vol. 366, pp. 177–187, 2016\.
  * [21] Y. Liang, S. T. Monteiro, and E. S. Saber, “Transfer learning for high resolution aerial image classification,” in _2016 IEEE Applied Imagery Pattern Recognition Workshop (AIPR)_. IEEE, 2016, pp. 1–8.
  * [22] S. Ji, S. Wei, and M. Lu, “A scale robust convolutional neural network for automatic building extraction from aerial and satellite imagery,” _International journal of remote sensing_ , vol. 40, no. 9, pp. 3308–3322, 2019.
  * [23] J. Liu, D. Strohschein, S. Samsi, and A. Weinert, “Large scale organization and inference of an imagery dataset for public safety,” in _2019 IEEE High Performance Extreme Computing Conference (HPEC)_ , Sep. 2019, pp. 1–6.
  * [24] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [25] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _2009 IEEE conference on computer vision and pattern recognition_. Ieee, 2009, pp. 248–255.
  * [26] K. Team, “Keras documentation: ResNet and ResNetV2.” [Online]. Available: https://keras.io/api/applications/resnet/#resnet50-function
  * [27] “torchvision.models — Torchvision 0.11.0 documentation.” [Online]. Available: https://pytorch.org/vision/stable/models.html
  * [28] B. Zhou, A. Khosla, A. Lapedriza, A. Oliva, and A. Torralba, “Learning deep features for discriminative localization,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2921–2929.
  * [29] S. Suzuki _et al._ , “Topological structural analysis of digitized binary images by border following,” _Computer vision, graphics, and image processing_ , vol. 30, no. 1, pp. 32–46, 1985.
  * [30] A. M. Andrew, “Multiple view geometry in computer vision,” _Kybernetes_ , 2001\.
  * [31] M. A. Fonstad, J. T. Dietrich, B. C. Courville, J. L. Jensen, and P. E. Carbonneau, “Topographic structure from motion: a new development in photogrammetric measurement,” _Earth surface processes and Landforms_ , vol. 38, no. 4, pp. 421–430, 2013.
  * [32] mapillary, “Opensfm,” https://github.com/mapillary/OpenSfM, Feb 2021. [Online]. Available: https://github.com/mapillary/OpenSfM
  * [33] C.-P. Wang, K. Wilson, and N. Snavely, “Accurate georegistration of point clouds using geographic data,” in _2013 International Conference on 3D Vision-3DV 2013_. IEEE, 2013, pp. 33–40.
  * [34] M. A. Fischler and R. C. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography,” _Communications of the ACM_ , vol. 24, no. 6, pp. 381–395, 1981.
  * [35] C. of Baton Rouge and P. of East Baton Rouge, “The great flood of 2016 story map,” https://ebrgis.maps.arcgis.com/apps/MapSeries/index.html?appid=1c4ac
9fca97846d2a1780a90fc68c6eb, Aug 2016. [Online]. Available:
https://ebrgis.maps.arcgis.com/apps/MapSeries/index.html?appid=1c4ac
9fca97846d2a1780a90fc68c6eb

##  Appendix A Flowchart

Figure 4: Flowchart depicting our approach.

##  Appendix B Labeling scheme

In the construction of the LADI dataset, images were shown to a variable
number of workers (generally between 3-5); each worker was asked to identify
which, if any, labels for a given category (e.g. “Damage") applied to that
image [23]. Responses from all workers were recorded. As a result, images
could have potentially differing annotations between workers due to factors
such as subjectivity (worker did not think the label applied) or error
(incorrect input). To account for these conflicts, we designate three
different labelling schemes for classifier training and evaluation:

  1. A)

$B_{i,j}>1$,

  2. B)

$B_{i,j}>2$,

  3. C)

$B_{i,j}>1$ and $B_{i,j}/w_{i}>\underset{\forall
i}{\mathrm{median}}\\{B_{i,j}/w_{i}\\}$,

where $B_{i,j}$ is the number of workers that labelled image $i$ as class $j$
and $w_{i}$ is the number of workers that labelled image $i$ at all. We
trained and tested using different combinations of these labelling scheme to
determine a balance between filtering out noise and preserving a sufficiently
representative dataset.

| Train
---
label
| Test
---
label
| Accuracy
---
(%)
| Precision
---
(%)
| Recall
---
(%)
A | A | 77 | 65 | 79
B | 71 | 38 | 91
C | 70 | 42 | 83
B | A | 77 | 75 | 53
B | 83 | 54 | 68
C | 80 | 55 | 64
C | A | 79 | 73 | 65
B | 80 | 48 | 80
C | 83 | 53 | 69
Table 2: Accuracy, precision and recall values for the three ResNet models.
Train label refers to the set of labels used in training, while Test label
refers to the set of labels against which each model was evaluated.

Table 2 shows the testing accuracy, precision and recall values for the three
ResNet50 classifiers that were trained (one for each training labelling scheme
defined above. In order to properly compare the three models, each of the
three classifiers was also evaluated against the remaining two labelling
schemes. Regardless of the labelling, the actual images that comprised the
testing set (as well as the training and validation sets) were the same for
all three schemes. For the purposes of this paper, we will refer to each of
the models according to their training labelling scheme.

Unsurprisingly, each of three models had the highest accuracy when compared
against the labelling scheme they were trained on. With the other two metrics,
though, there are noticeable trends. In terms of precision, model B had the
highest precision when evaluated against any labelling scheme, followed by C
and finally A. With recall, the opposite holds: A has the highest recall
across the board, followed by C and then B. These trends are not difficult to
justify, since B necessarily has a higher standard for classification as
flooding than A. For flooding, C is a compromise between the most lenient
labelling scheme (A) and the strictest one (C). In this particular
application, we consider false positives to be less serious than false
negatives; that is, we would rather think that someone was in danger from
flooding when they are not (false positive) than think that they are not in
danger when they are (false negative). As such, we proceed using model A for
the remainder of the section.

##  Appendix C CAM details

Using the terminology in [28], the output on the final fully connected layer
is given by:

$S_{c}=\sum_{k}w_{k}^{c}\sum_{x,y}f_{k}(x,y)=\sum_{x,y}\sum_{k}w_{k}^{c}f_{k}(x,y),$
(1)

where $w_{k}^{c}$ is the weight corresponding to class $c$ for the $k$-th unit
within conv5 (the final block within ResNet-50) and $f_{k}(x,y)$ is the
activation of the same $k$-th unit at location ($x$, $y$) (such that
$\sum_{x,y}f_{k}(x,y)$ is the output of the global pooling layer). Let
$M_{c}(x,y)=\sum_{k}w_{k}^{c}f_{k}(x,y)$, so that:

$S_{c}=\sum_{x,y}M_{c}(x,y).$ (2)

Here, $M_{c}(x,y)$ can be viewed as a measure of importance of a spatial
coordinate ($x$, $y$) for the class $c=\text{{flooding/water damage}}$, and
hence referred to the class activation map. In order to determine the
boundaries of the flooding instances, we threshold on $M_{c}$:

$M^{\text{mask}}_{c}(x,y)=\begin{cases}1&\mbox{if }M_{c}(x,y)\geq 0\\\
0&\mbox{otherwise}\end{cases}$ (3)

##  Appendix D CAM qualitative evaluation

(a)

(b)

(c)

(d)

(e)

(f)

Figure 5: Sample of CAP images identified as flooding by ResNet model and
their associated damage polygons.

Figure 5 shows a sample of LADI images that were classified as having
_flooding/water damage_ , along with the estimated extent of flooding for
qualitative evaluation. We can see that the CAM provides a decent coarse
estimate of the extent of water in the image. Flooding is slightly more
complicated. While Figures 5(a) and 5(b) very clearly show flooding events,
the top portion of Figure 5(c) seems to simply be picking up the shoreline. As
an important note, we noticed that many images that show large bodies of water
also tend to include the horizon in the flooding polygon (e.g. Figure 5(b)).
This might be because flooding typically covers a large portion of area, and
therefore images that include the horizon might be more likely to also include
flooding. This underscores the importance of filtering images with large
footprints after georeferencing. Figures 5(d), 5(e) and 5(f) are images that
were identified as flooding from the Louisiana 2016 floods. Even in this case
where many images have large portions of flooding, our approach is still able
to trace the extent of the water.

##  Appendix E Closeup comparison

Figure 6 provides a closeup comparison of the footprint (SfM+binary
classification) and (SfM+CAM) approaches. Precision is the total area colored
dark blue divided by the sum of the dark blue and red areas.

(a) Image footprint

(b) Our approach

Figure 6: Close-up of flooding estimates for image footprint and our approach,
showing true and false positive regions.


# Some coset actions in $G_{2}(q)$ and distance-transitive graphs

Jianxiang Chen

###### Abstract

This paper studies whether there are distance-transitive graphs arising from
the coset actions of $G_{2}(q)$ on the subfield subgroup $G_{2}(\sqrt{q})$ or
$G_{2}(q)$ on the Ree subgroup ${}^{2}G_{2}(q)$. It is found that there are no
such graphs, even if the groups are extended by outer automorphisms of
$G_{2}(q)$.

##  1 Introduction

In this paper, a graph means a finite connected undirected graph without loops
or multiple edges. A graph $\Gamma$ is called distance-transitive if for every
two pairs $(w,x)$ and $(y,z)$ of the graph such that the distance from $w$ to
$x$ is the same as the distance from $y$ to $z$, there is an automorphism of
the graph that carries $w$ to $y$ and $x$ to $z$.

By a result of D.H.Smith[1], distance-transitive graphs can be classified into
either primitive or non-primitive, and non-primitive distance-transitive
graphs can be derived from primitive distance-transitive graphs, so the
classification of primitive distance-transitive graphs serves as a step to
classify all distance-transitive graphs.

Praeger, Saxl and Yokoyama[2] showed that a primitive distance-transitive
graph is either a Hamming graph, has an automorphism group of affine type, or
has an almost-simple automorphism group (a group $G$ is almost simple if there
is a nonabelian simple group $H$ such that $H\subset G\subset\text{Aut}(H)$;
here $H$ is the socle of $G$). The primitive distance-transitive graphs having
automorphism groups of affine type are classified by John van Bon[3].

The vertex stabilizer in a primitive distance-transitive graph $\Gamma$ is a
maximal subgroup of $\text{Aut}\Gamma$. Thanks to the classification of all
finite simple groups and their maximal subgroups, the classification of
primitive distance-transitive graphs with almost-simple automorphism groups
can be dealt with on a case-by-case basis. A lot of work has already been
done; for example, the graphs $\Gamma$ where $\text{Aut}\Gamma$ have
alternating, sporadic or linear socle are completely determined in [4], [5]
and [6] respectively.

There is a combinatorial generalization of distance-transitive graphs called
distance-regular graphs: a distance-regular graph is a regular graph such that
for any two vertices $x$ and $y$, the number of vertices at distance $i$ from
$x$ and at distance $j$ from $y$ is independent from $x$ and $y$, and only
dependent upon $i$, $j$ and the distance between $x$ and $y$. It is evident
from the definition that every distance-transitive graph is distance-regular,
because every ordered pair $(x,y)$ of vertices with the same distance between
$x$ and $y$ are equivalent. Distance-regular graphs are usually characterized
by intersection arrays.

In this paper we investigate two open cases where $\text{Aut}\Gamma$ has socle
$G_{2}(q)$: they correspond to the vertex stabilizer having type
$G_{2}(\sqrt{q})$ and ${}^{2}G_{2}(q)$. More formally, we assume that
$\text{Aut}\Gamma=G_{2}(q)\text{:}X$ where $X$ is a subgroup of the outer
automorphism group of $G_{2}(q)$. The vertex stabilizer of $\Gamma$ is
$G_{2}(\sqrt{q})\text{:}X$ and ${}^{2}G_{2}(q)\text{:}X$, respectively. So the
vertices of $\Gamma$ can be identified with the cosets
$(G_{2}(q)\text{:}X)/(G_{2}(\sqrt{q})\text{:}X)$ and
$(G_{2}(q)\text{:}X)/(^{2}G_{2}(q)\text{:}X)$, respectively.

##  2 $G_{2}(q)$ on $G_{2}(\sqrt{q})$

Let $G$ be the finite simple group $G_{2}(q)$, where $q=p^{2n}$, and $H$ the
subgroup of $G$ isomorphic to the subfield subgroup $G_{2}(\sqrt{q})$; all
such subgroups are pairwise conjugate in $G$[7,8]. Let $X$ be a subgroup of
the outer automorphism group of $G$. Let $r=\sqrt{q}$. Let $\sigma$ be the
Frobenius isomorphism $\sigma:x\rightarrow x^{r}$.

The first thing to note is that $q$ is a power of $3$. If $\Gamma$ is
distance-transitive, the permutation character of $\text{Aut}\Gamma$ acting on
the vertices of $\Gamma$ is multiplicity-free[3]. The multiplicity-free
actions of $(G\text{:}X)/(H\text{:}X)$ are determined in [9]: The action is
multiplicity-free iff $q$ is a power of $3$ and $X$ contains the graph
automorphism of $G_{2}(q)$. So $q$ is a power of $3$.

Ross Lawther has computed the suborbit lengths of $G$ acting on $G/H$ when $q$
is a power of $3$[10], shown in Table 1, where $z$ is the
$G_{2}(\bar{\mathbb{F}}_{q})$-class representative of $x^{-1}\sigma(x)$ in
$G_{2}(q)$ listed in [11].

The elements of the form $x_{ma+nb}(1)$ are unipotent elements of the
algebraic group $G_{2}(\bar{\mathbb{F}}_{q})$, so they have order $3$. Note
that $x_{2a+b}(1)$ and $x_{3a+2b}(1)$ commute[10], so
$x_{2a+b}(1)x_{3a+2b}(1)$ also has order $3$.

Let $T$ be a Cartan subgroup of the algebraic group
$G_{2}(\bar{\mathbb{F}}_{q})$. The Dynkin diagram with respect to $T$ is of
type $G_{2}$. Denote its short simple root as $a$ and long simple root as $b$
under a choice of simple roots. Then $z_{1}=a+b$, $z_{2}=a$, $z_{3}=-2a-b$ are
three short roots of the root diagram. The elements
$h(x_{1},x_{2},x_{3})$$(x_{1},x_{2},x_{3}\in\bar{\mathbb{F}}_{q}^{*})$ are
elements in $T$, mapping $z_{i}$ to $x_{i}$, $i=1,2,3$[11].

The letters $\sigma$, $\tau$, $\theta$, $\eta$ and $\gamma$ in Table 1
represents certain elements of the multiplicative group
$\mathbb{F}_{q^{3}}^{*}$. Let $\kappa$ be a generator of the multiplicative
group $\mathbb{F}_{q^{3}}^{*}$, and

$\sigma=\kappa^{(r+1)(r^{3}-1)}$, |  $\tau=\kappa^{(r-1)(r^{3}+1)}$, |  $\theta=\kappa^{q^{2}+q+1}$,
---|---|---
$\eta=\theta^{r-1}$, |  $\gamma=\theta^{r+1}$. |

The shorthand $h_{*}(x_{1},x_{2},x_{3})$ represents
$h(*^{x_{1}},*^{x_{2}},*^{x_{3}})$ where $*$ is any letter.

$z$ | Size of suborbits | Number of classes
---|---|---
$1$ | $1$ | $1$
$x_{3a+2b}(1)$ | $(r^{6}-1)$ | $1$
$x_{2a+b}(1)$ | $(r^{6}-1)$ | $1$
$x_{2a+b}(1)x_{3a+2b}(1)$ | $(r^{6}-1)(r^{2}-1)$ | $1$
$x_{a+b}(1)x_{3a+b}(1)$ | $r^{2}(r^{6}-1)(r^{2}-1)/2$ | $1$
| $r^{2}(r^{6}-1)(r^{2}-1)/2$ | $1$
$x_{a}(1)x_{b}(1)$ | $r^{4}(r^{6}-1)(r^{2}-1)$ | $1$
$h(-1,-1,1)$ | $r^{4}(r^{4}+r^{2}+1)$ | 1
$h(-1,-1,1)x_{b}(1)$ | $r^{4}(r^{6}-1)$ | 1
$h(-1,-1,1)x_{2a+b}(1)$ | $r^{4}(r^{6}-1)$ | 1
$h(-1,-1,1)x_{b}(1)x_{2a+b}(1)$ | $r^{4}(r^{6}-1)(r^{2}-1)/2$ | 1
| $r^{4}(r^{6}-1)(r^{2}-1)/2$ | 1
$h_{\gamma}(i,-2i,i)$ | $r^{5}(r^{3}-1)(r^{2}-r+1)$ | $(r-3)/2$
$h_{\gamma}(i,-2i,i)x_{3a+2b}(1)$ | $r^{5}(r^{6}-1)(r-1)$ | $(r-3)/2$
$h_{\gamma}(i,-i,0)$ | $r^{5}(r^{3}-1)(r^{2}-r+1)$ | $(r-3)/2$
$h_{\gamma}(i,-i,0)x_{2a+b}(1)$ | $r^{5}(r^{6}-1)(r-1)$ | $(r-3)/2$
$h_{\gamma}(i,j,-i-j)$ | $r^{6}(r^{3}-1)(r^{2}-r+1)(r-1)$ | $(r^{2}-8r+15)/12$
$h_{\eta}(i,-2i,i)$ | $r^{5}(r^{3}+1)(r^{2}+r+1)$ | $(r-1)/2$
$h_{\eta}(i,-2i,i)x_{3a+2b}(1)$ | $r^{5}(r^{6}-1)(r+1)$ | $(r-1)/2$
$h_{\eta}(i,-i,0)$ | $r^{5}(r^{3}+1)(r^{2}+r+1)$ | $(r-1)/2$
$h_{\eta}(i,-i,0)x_{2a+b}(1)$ | $r^{5}(r^{6}-1)(r+1)$ | $(r-1)/2$
$h_{\eta}(i,j,-i-j)$ | $r^{6}(r^{3}+1)(r^{2}+r+1)(r+1)$ | $(r^{2}-4r+3)/12$
$h_{\theta}(i,(r-1)i,-ri)$ | $r^{6}(r^{6}-1)$ | $(r-1)^{2}/4$
$h_{\theta}(i,ri,-(r+1)i)$ | $r^{6}(r^{6}-1)$ | $(r-1)^{2}/4$
$h_{\tau}(i,ri,r^{2}i)$ | $r^{6}(r^{3}-1)(r^{2}-1)(r+1)$ | $r(r+1)/6$
$h_{\sigma}(i,-ri,r^{2}i)$ | $r^{6}(r^{3}+1)(r^{2}-1)(r-1)$ | $r(r-1)/6$
Table 1: The suborbits of the coset action $G/H$ when $q$ is a power of $3$.

The second thing to note is that the subgroup $G_{2}(\sqrt{q})$ is the fixed
subgroup of the Frobenius isomorphism $\sigma:x\rightarrow x^{\sqrt{q}}$. If
$\sigma\in X$, then the subgroup $H\text{:}X$ is an involution centralizer in
$G\text{:}X$, and the action of $G\text{:}X$ on cosets
$(G\text{:}X)/(H\text{:}X)$ can be identified with the action of $G\text{:}X$
on the conjugacy class of $\sigma$ by conjugation. Then it would be possible
to apply the methodology of [12], summarized in the following theorem:

######  Theorem 2.1.

Let $\Gamma$ be a distance-transitive graph with distance-transitive group
$G$. Suppose that the vertex set $V\Gamma$ of $\Gamma$ is a conjugacy class of
involutions in $G$, that $G$ acts on $\Gamma$ by conjugation and that there
are elements in $V\Gamma$ which commute in $G$. Take $x,y\in\Gamma$ with $x$
adjacent to $y$. Then at least one of the following statements holds.

· $\Gamma$ is a polygon or an antipodal 2-cover of a complete graph.

· $G$ is a 2-group.

· The order of $xy$ is an odd prime, if $a,b\in\Gamma$ with $ab$ of order $2$,
then $a$ and $b$ have maximal distance in $\Gamma$, and if $a,b\in\Gamma$ the
order of $ab$ is not 4.

· The elements $x$ and $y$ commute, and if $z\in O_{2}(x)$ then $xz$ has order
$2$, $4$ or an odd prime. Moreover either $O_{2}(C_{G}(x))=\langle x\rangle$
or $C_{G}(x)$ contains a normal subgroup generated by $p$-transpositions.

By the following lemma of [12], we can assume $\sigma\in X$:

######  Lemma 2.1.

Let $\Gamma$ be a graph on which $G$ acts primitively distance-transitively,
and denote by $H$ the stabilizer in $G$ of a vertex of $\Gamma$. Suppose
$\sigma$ is an automorphism of $G$.

· If $\sigma$ centralizes $H$ and diam $\Gamma\geq 3$, then
$\sigma\in\text{Aut}(\Gamma)$;

· If $\sigma$ normalizes $H$ and diam $\Gamma\geq 5$, then the same conclusion
holds.

The suborbit lengths shown in Table 1 indicates that a distance-transitive
$\Gamma$ cannot have diameter $2$ (because there are at least $3$ different
nontrivial suborbit lengths in $G$ acting on $G/H$, and the outer automorphism
group can only fuse together suborbits of the same length). So we may assume
$\Gamma$ has diameter $\geq 3$ and thus $\sigma\in X$.

In the rest of this section, we will denote the elements of $G\text{:}X$ in
external semidirect product notation; that is, an element of $G\text{:}X$ is
written as $(x,y)$, where $x\in G$ and $y\in X$, and the multiplication rule
is $(w,x)(y,z)=(wx(y),xz)$. Thus, the conjugation of $(1,\sigma)$ by $(g,1)$
is $(g^{-1},1)(1,\sigma)(g,1)=(g^{-1},\sigma)(g,1)=(g^{-1}\sigma(g),\sigma)$.
Also $(g^{-1}\sigma(g),\sigma)(1,\sigma)=(g^{-1}\sigma(g),1)$. If $(1,\sigma)$
commutes with $(g^{-1}\sigma(g),\sigma)$, we have
$g^{-1}\sigma(g)=\sigma(g^{-1}\sigma(g))$. And that means
$(g^{-1}\sigma(g))^{2}=g^{-1}\sigma(g)g^{-1}\sigma(g)=g^{-1}\sigma(g)\sigma(g^{-1}\sigma(g))=1$.
The reverse implication also holds, in the sense that
$(g^{-1}\sigma(g))^{2}=1$ implies $(1,\sigma)$ commutes with
$(g^{-1}\sigma(g),\sigma)$.

There exists elements $g\in G$ such that $g^{-1}\sigma(g)$ is conjugate to
$h(-1,-1,1)$. In this case, $g^{-1}\sigma(g)$ has order $2$, so $(1,\sigma)$
commutes with $(g^{-1}\sigma(g),\sigma)$. Thus the assumptions of Theorem 2.1
holds.

To find an element with the form $(g^{-1}\sigma(g),\sigma)$ that is connected
to $(1,\sigma)$, the following theorem[3] is applied:

######  Theorem 2.2.

Let $G$ be a primitive distance-transitive group of automorphisms of $\Gamma$
(having diameter $d$) and $x\in V\Gamma$ . Then among the nontrivial
$G_{x}$-orbit lengths, $|\Gamma_{1}(x)|$ $(\Gamma_{i}(x)$ means the vertices
of $\Gamma$ having distance $i$ to $x)$ is among the two smallest. Moreover,
if $|\Gamma_{1}(x)|$ is not the smallest, then $|\Gamma_{d}(x)|$ is.

Since outer automorphisms can only fuse suborbits with the same length, the
smallest suborbits must be one labeled by $x_{3a+2b}(1)$, $x_{2a+b}(1)$ or
$x_{2a+b}(1)x_{3a+2b}(1)$. In either case, the element $g^{-1}\sigma(g)$ has
order $3$, so $(1,\sigma)$ and $(g^{-1}\sigma(g),\sigma)$ does not commute. So
the last case of Theorem 2.1 does not hold. As $G\text{:}X$ is not a 2-group
and $\Gamma$ has degree and diameter at least $3$, the first and second case
does not hold. It can be concluded that if $\Gamma$ is distance-transitive,
then the third case of Theorem 2.1 holds. Specifically, there are no $g\in
G\text{:}X$ such that $g^{-1}\sigma(g)$ has order $4$.

There exists $g\in G$ such that $g^{-1}\sigma(g)$ is conjugate to
$h_{\gamma}(i,-2i,i)$ when $r\geq 9$, and there exists $g\in G$ such that
$g^{-1}\sigma(g)$ is conjugate to $h_{\eta}(i,-2i,i)$. The elements $\gamma$
and $\eta$ has order $r-1$ and $r+1$, respectively. As one of $r-1$ and $r+1$
is divisible by $4$, it is possible to choose $i$ such that one of
$\gamma^{i}$ and $\eta^{i}$ has order $4$ in the multiplicative group
$\mathbb{F}_{q^{3}}^{*}$. But this means that $g^{-1}\sigma(g)$ has order $4$.

So there is no primitive distance-transitive graph with automorphism group
$G_{2}(q)\text{:}X$ and vertex stabilizer $G_{2}(\sqrt{q})\text{:}X$.

##  3 $G_{2}(q)$ on ${}^{2}G_{2}(q)$

Let $G$ be the finite simple group $G_{2}(q)$, where $q=3^{2n+1}$ ($n\geq 0$),
and $H$ the subgroup of $G$ isomorphic to the Ree group ${}^{2}G_{2}(q)$; all
such subgroups are pairwise conjugate in $G$[7]. Let $X$ be a subgroup of the
outer automorphism group of $G$.

Ross Lawther has computed the suborbit lengths of $G$ acting on $G/H$[10]:

Size of suborbits | Number of classes
---|---
$1$ | $1$
$(q^{3}+1)(q-1)$ | $1$
$q(q^{3}+1)(q-1)/2$ | $1$
$q(q^{3}+1)(q-1)/2$ | $1$
$q^{2}(q^{3}+1)(q-1)$ | $1$
$q^{2}(q^{2}-q+1)$ | $1$
$q^{2}(q^{3}+1)(q-1)/2$ | $1$
$q^{2}(q^{3}+1)(q-1)/2$ | $1$
$q^{3}(q^{3}+1)$ | $(q-3)/2$
$q^{3}(q^{2}-q+1)(q-1)$ | $(q-3)/6$
$q^{3}(q^{2}-1)(q-3m+1)$ | $(q-3m)/6$
$q^{3}(q^{2}-1)(q+3m+1)$ | $(q+3m)/6$
Table 2: The suborbits of the coset action $G/H$. Note: $q=3m^{2}$

Note that three rows of this table would be absent if $q=3$; but in this case,
the graph would have $|G|/|H|=4245696/1512=2808$ vertices and diameter at
least $6$ (because the outer automorphism group can only fuse together
suborbits of the same length). A graph of this size would be covered in
Chapter 14. of [13], but [13] does not contain any intersection arrays of a
distance-regular graph with $2808$ vertices and diameter at least $6$. So we
will assume $q\geq 27$ in the rest of this section.

An inequality from [14] states that a distance-regular graph of diameter $d$
and $v$ vertices satisfies $d<8/3\log_{2}(v)$. If there were a distance-
regular graph arising from the group action, it would have
$q^{3}(q^{3}-1)(q+1)$ vertices and diameter at least
$(q+6)/|X|=(q+6)/2(2n+1)$, because the outer automorphism group of $G$ is a
direct product of the graph automorphism (of order $2$) and the field
automorphism (of order $2n+1$), and it can never fuse more than $|X|$
suborbits into a suborbit. This inequality is only satisfied when $n\leq 3$.

The main theorem to deal with the cases when $n\leq 3$ is the following
theorem from [12]:

######  Theorem 3.1.

Let $\Gamma$ be a graph of diameter $d$ on which the group $G$ acts distance-
transitively as a group of automorphisms. For a vertex $x\in\Gamma$, denote by
$G_{x}^{i}$ the kernel of the action of the stabilizer of $x$ in $G$ on
$\Gamma_{i}(x)$. If, for some $i\geq 1$, we have $G_{x}^{i}\neq 1$, then
$G^{i}_{x}\subsetneq G^{i-1}_{x}\subsetneq...\subsetneq G^{1}_{x}$ or
$G^{i}_{x}\subsetneq G^{i+1}_{x}\subsetneq...\subsetneq G^{d}_{x}$.

Since all the suborbit lengths are proper divisors of
$|H|=q^{3}(q^{3}+1)(q-1)$, the kernel of $H$ acting on any of the suborbits is
nontrivial, and so does the extension $H\text{:}X$.

The last two rows of Table 2 contain two suborbits. The respective kernel size
(the size of $G_{x}^{i}$) of one row is divisible by $19$ when $n=1$, $31$
when $n=2$, $43$ when $n=3$, and the other divisible by $37$ when $n=1$, $271$
when $n=2$, $2269$ when $n=3$. By Theorem 2.2, the suborbit corresponding to
$\Gamma_{1}(x)$ has length $(q^{3}+1)(q-1)$ or $q^{2}(q^{2}-q+1)$. Thus
$G^{1}_{x}$ is not divisible by any of the two kernel sizes, and it is
impossible to have $G^{i}_{x}\subsetneq G^{1}_{x}$ for any of the two
suborbits. So $G^{i}_{x}\subsetneq G^{d}_{x}$ for both suborbits, and
$G^{d}_{x}$ would have order divisible by the primes $19\times 37$ when $n=1$,
$31\times 271$ when $n=2$, and $43\times 2269$ when $n=3$. But no suborbit has
such a kernel, even if $X$ is nontrivial (outer automorphisms can only
multiply the order of the kernels by some number containing the prime factors
$2$, $3$, $5$ and $7$.).

So there is no primitive distance-transitive graph with automorphism group
$G_{2}(q)\text{:}X$ and vertex stabilizer ${}^{2}G_{2}(q)\text{:}X$.

## References

1\. Smith, Derek H. ”Primitive and imprimitive graphs.” The Quarterly Journal
of Mathematics 22.4 (1971): 551-557.

2\. Praeger, Cheryl E., Jan Saxl, and Kazuhiro Yokoyama. ”Distance transitive
graphs and finite simple groups.” Proceedings of the London Mathematical
Society 3.1 (1987): 1-21.

3\. van Bon, John. ”Finite primitive distance-transitive graphs.” European
Journal of Combinatorics 28.2 (2007): 517-532.

4\. Liebeck, Martin W., Cheryl E. Praeger, and Jan Saxl. ”Distance transitive
graphs with symmetric or alternating automorphism group.” Bulletin of the
Australian Mathematical Society 35.1 (1987): 1-25.

5\. Ivanov, A. A., et al. ”Distance-transitive representations of the sporadic
groups.” Communications in Algebra 23.9 (1995): 3379-3427.

6\. van Bon, John, and Arjeh M. Cohen. ”Linear groups and distance-transitive
graphs.” European Journal of Combinatorics 10.5 (1989): 399-411.

7\. Kleidman, Peter B. ”The maximal subgroups of the Chevalley groups
$G_{2}(q)$ with $q$ odd, the Ree groups ${}^{2}G_{2}(q)$, and their
automorphism groups.” Journal of Algebra 117.1 (1988): 30-71.

8\. Cooperstein, Bruce N. ”Maximal subgroups of $G_{2}(2^{n})$.” Journal of
Algebra 70.1 (1981): 23-36.

9\. Lawther, R. ”Some (almost) multiplicity-free coset actions.” Groups,
Combinatorics and Geometries, in: LMS Lecture Note Series 165 (1992).

10\. Lawther, R. ”Some coset actions in $G_{2}(q)$.” Proceedings of the London
Mathematical Society 3.1 (1990): 1-17.

11\. Enomoto, Hikoe. ”The conjugacy classes of Chevalley groups of type
$G_{2}$ over finite fields of characteristic 2 or 3.” Journal of the Faculty
of Science, University of Tokyo. Sect. 1, Mathematics, astronomy, physics,
chemistry 16.3 (1970): 497-512.

12\. van Bon, John. ”On distance-transitive graphs and involutions.” Graphs
and Combinatorics 7.4 (1991): 377-394.

13\. A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular Graphs,
Ergebnisse der Mathematik 3.18, Springer-Verlag, Heidelberg, (1989).

14\. Bang, Sejeong, Akira Hiraki, and Jacobus H. Koolen. ”Improving diameter
bounds for distance-regular graphs.” European Journal of Combinatorics 27.1
(2006): 79-89.