# Contour Completion using Deep Structural Priors

Ali Shiraee†
Department of Computer Science
Kharazmi University &Morteza Rezanejad†
Department of Psychology
University of Toronto
&Mohammad Khodadad
Faculty of Engineering
McMaster University
&Dirk B. Walther
Department of Psychology
University of Toronto
&Hamidreza Mahyar
Faculty of Engineering
McMaster University Dr. Morteza Rezanejad contributed to this article in his
personal capacity as an adjunct researcher at the University of Toronto.
†These authors made equal contributions to this article.
Corresponding author: Morteza Rezanejad (morteza.rezanejad@utoronto.ca).

###### Abstract

Humans can easily perceive illusory contours and complete missing forms in
fragmented shapes. This work investigates whether such capability can arise in
convolutional neural networks (CNNs) using deep structural priors computed
directly from images. In this work, we present a framework that completes
disconnected contours and connects fragmented lines and curves. In our
framework, we propose a model that does not even need to know which regions of
the contour are eliminated. We introduce an iterative process that completes
an incomplete image and we propose novel measures that guide this to find
regions it needs to complete. Our model trains on a single image and fills in
the contours with no additional training data. Our work builds a robust
framework to achieve contour completion using deep structural priors and
extensively investigate how such a model could be implemented.

##  1 Introduction

The human visual system is used to seeing incomplete outlines. Our brains can
effortlessly group visual elements and fragmented contours that seem to be
connected to each other. This power enables us to make shapes, organize
disconnected visual features, and even properties of 3D surfaces when
projected on 2D planes. [1] demonstrated how early vision may quickly complete
partially-occluded objects using monocular signals. This capability of
perceptual grouping has been studied in vision science for decades [2, 3, 4,
5]. Although there has been some work on perceptual grouping [6, 7, 8, 9] in
the past couple of years, it has been less studied in the past decade due to
the enormous progress of deep neural networks and their success in dealing
with the pixel-by-pixel inference of images.

Different types of lines and curves have been studied to maximize the
connectivity of two broken ends in the planer contour completion problem [10,
11, 12]. Different types of lines and curves have been studied to maximize the
connectivity of two broken ends in the planer contour completion problem.
Geometry-based constraints can be utilized to address some challenges of
contour completion problems, such as smoothness and curvature consistency [13,
14, 15, 16]. However, such approaches only work for simple, smooth contours
and usually fail in more complex settings.

On the other hand, we currently have deep models that could easily take an
incomplete image and complete the missing regions using enough training data
[17, 18, 19]. The amazing capability of such models especially those that are
trained on different modalities with millions or billions of training data
[20, 21, 22] raises the question of whether we need such a large amount of
training to perceive all the visual cues that are present in an image, which
underlies visual perception by humans. In human vision, Gestalt psychology
[23] suggests that our brain is designed to perceive structures and patterns
that are grouped by some known rules. In this work, we show that some
perceptual structures can also be learned from the image itself directly using
architectures that enable such learning. Earlier work has shown that some
forms of perceptual grouping can be achieved using computational models, such
as stochastic completion fields [24, 25, 26]. This type of learning resonates
with some of the Gestalt perceptual grouping principles including “proximity”,
“good continuation” and “similarity”. In scenarios where color and/or texture
are present, the cue of “similarity” helps us group regions with consistent
patterns [27]. When color and texture are present, they provide a collection
of rich information for such cues. In the present article, we probe
convolutional neural networks in a scenario where both are absent, and the
neural network is dealing with just forms and shapes.

Specifically, we explore whether the convolutional neural network architecture
itself can give rise to some of these grouping cues when they are fed just
contours and shapes alone. For years, neural networks have been treated as
black boxes that can generalize images very well to multiple classes when
there are enough training exemplars. One of the reasons that neural networks
are trained on many exemplars is to avoid the problem of overfitting. On the
other hand, we know that CNNs that generalize well to large classes of
exemplars can easily overfit when those class labels are randomly permuted
[28]. Inspired by this observation, [29] suggest that image priors can be
learned to a large extent through a generator network architecture [30] that
is solely trained on a single image. This encouraged us to take a deeper look
at what structural information can be learned from a single-shape image and
whether we can reconstruct some of those perceptual grouping capabilities
using a generator network.

Inspired by [28, 29], in this work, we adopt a novel training regime to
complete shapes and contours where we use a UNet architecture [31] with random
initial weights and try to complete the contours within a single image without
any training data. In our model, we imagine that the input image (i.e., the
only image used to update the model’s weights) is an image of fragmented
contours. In this work, instead of training the model on multiple images
fetched from a big image dataset, we imagine a random fixed tensor noise image
as input to this model. At each iteration, the random noise tensor is inferred
through our generative network and the network produces an outcome image. We
introduce a novel loss function that enables this network to complete
contours. This process repeats, and the weights of our network are updated
gradually based on this loss function, which is an energy term defined based
on the input image and the output of the network.

---
(a) |  (b)
Figure 1: Just by looking at subfigure (a), we, as humans, can easily perceive
a shape like the one in subfigure (b). This is an extraordinary capability of
our human brain and in this paper, we tried to see whether convolutional
neural networks can show such capabilities.

The model will reconstruct the missing structures i.e., group fragmented
contours that perceptually seem to be connected, before it fully overfits to
the incomplete input image. Contributions of our work are summarized as
follows:

  1. 1.

In our pipeline, we propose a novel algorithm that enables us to complete
contours that appear to be connected to each other in an illusory form.

  2. 2.

Our model is trained on just one single query image and does not need any
training data.

  3. 3.

Our model does not need to know which regions of the image are masked or
occluded, i.e., we remove the dependency of the algorithm on the guiding mask
(a guiding mask is a mask that informs the model on where the missing regions
are located at).

  4. 4.

We also introduce two metrics to produce a stopping criterion to know when to
stop training before the model fully overfits to the incomplete image, i.e.,
we guide the model to stop when the completed image is produced.

Figure 2: The trajectory from random noise $X_{N}$ to the incomplete image
$X_{I}$ in image space. The network will pass a completed version of the
image, $X_{C}$, throughout this trajectory.

##  2 Methods

Our eyes are trained to predict a missing region of an occluded object within
a scene. We can easily perceive or make guesses about parts of objects or
shapes that we do not necessarily see. Even when we are looking at an image,
we might guess about the shape, property, or other attributes of an unknown
object within a scene. Such capability extends beyond just known objects or
shapes. We can look at a disconnected set of contours and guess what the
connected form may look like. This capability is rooted in our prior knowledge
about the world. (see Figure 1).

Figure 3: This figure shows the architecture of our model, which is based on
the UNet-like hourglass architecture with skip-connection used in [29].

In this work, we aim to achieve a similar capability using deep generative
networks. Most neural networks that we work with these days are trained with a
massive amount of data and one might think that this is the only way that a
neural network can obtain prior information. Authors of Deep Image Prior (DIP)
[29] suggest that the convolutional architecture can capture a fair amount of
information about image distribution. They show that the hourglass
architectures like UNet [31] can show some good performances in some inverse
problems such as image denoising, super-resolution, and inpainting.

Figure 4: This figure shows our iterative process to complete the fragmented
contours of an image given as input to our pipeline.

In this work, we focus on completing fragmented contours end-to-end just by
using a single image. To be able to address this problem, we first look at a
similar problem in image editing, known as image inpainting. Image inpainting
is the task of completing an image where some regions of that image are
covered or filtered by a mask. In image inpainting, the generative model
receives a masked image with the mask that guides the algorithm to fill in
those missing regions. Although in the problem of contour completion, we have
a very similar goal, the additional challenge that we suffer from is that we
do not necessarily have a mask that covers the regions of interest for us. For
example, when we look at Figure 1 (left), we are not provided that which
regions of the image are incomplete by a guiding mask. Our brain figures this
out just by looking at the form and predicting those missing regions.

Inspired by the image inpainting work of DIP [29], we propose a novel
algorithm for the contour completion problem (see Figure 3), where, unlike
DIP, we do not have a guiding mask to know where to fill in the missing
regions of our disconnected contours.

Let us assume that we are given a degraded image $x_{I}$ containing a
fragmented contour. We propose an iterative process (see Figure 4) that can
connect those discontinuities and glue those fragmented pieces together as
follows. We propose an hour-glass model structure ($f$) that is initially set
up with completely random parameters ($\theta_{0}$) at first. Through an
iterative process, we start feeding our network with a fixed random tensor
noise $z$ signal and obtain the inferred output ($f(z)$) from that network. We
then back-propagate the difference between the inferred output and the
incomplete image to the network. We then repeat this process until the
difference between the generated outcome of the network ($f_{\theta}(z)$) and
the incomplete image ($x_{I}$) gets smaller and smaller and finally overfits
the incomplete image ($x_{I}$). In this work, we propose a novel error metric
to backpropagate in the model and update its weights. we set the metric in a
way that enables us to complete the incomplete image before it overfits the
incomplete image. This is where the magic of our algorithm happens. We also
propose a stopping criterion, so that when the image is complete, we no longer
overfit the outcome of the model and instead produce a plausible connected set
of fragmented contour pieces. As illustrated in Figure 2, this trajectory will
pass through a complete version of the image in image space, which is close to
the actual connected ground truth $x_{gt}$, which we do not have access to
directly.

###  2.1 Energy Function

We can model this iterative process mathematically by maximizing a posterior
distribution. Let us assume that the optimal image $x^{*}$ that we want to
achieve is on a path that connects a random tensor noise $z$ to the incomplete
image $x_{I}$. With this assumption, we can eventually overfit any random
tensor noise to the incomplete image $x_{I}$, and we can formulate the
posterior distribution of our wanted optimal image $x^{*}$ as follows:

$x^{*}=\operatorname*{argmax}_{x}p(x|x_{I}),$

To better recapitulate what we want to achieve using our generative model, we
solve an energy minimization problem on the parameter space of the model,
rather than explicitly working with probability distributions and optimizing
on $x$ (image space). Thus, we solve an energy minimization problem that
incorporates the incomplete image ($x_{I}$) and model parameters
($f_{\theta}(z)$):

$\theta^{*}=\operatorname*{argmin}_{\theta}E(f_{\theta}(z);x_{I}),\qquad
x^{*}=f_{\theta^{*}}(z)$

As shown in Figure 4, the pipeline starts from a random initialized set of
parameters $\theta$ and updates those weights until it reaches a local minimum
$\theta^{*}$. The only information provided for the network is the incomplete
image $x_{I}$. When we reach the optimal $\theta^{*}$, the completed image is
obtained as $x^{*}=f_{\theta^{*}}(z)$ where $z$ is random tensor noise. In
this work, we use a U-Net architecture with skip connections as the generator
model.

As we mentioned previously, in this work we were inspired by an earlier work
known as Deep Image Prior (DIP) [29]. In this work, the authors suggested a
mean-squared-error loss term that enables the network to compare the output of
the generator to the incomplete input image:

$E(x;x_{I})=\left\|(x-x_{I})\odot m\right\|\ ^{2}$ (1)

where $x_{I}$ is the incomplete image with missing pixels in correspondence of
a binary mask $m\in\left\\{0,1\right\\}^{H\times W}$ and $\odot$ operator is
for point-wise multiplication of two image matrices. In the inpainting tasks,
the existence of a mask is essential as the algorithm needs to know where to
fill in the missing area, whereas, in our work, we wanted to know whether the
network can perform completion on its own without the need for the mask. In
other words, is it possible for the network to predict where to fill in at the
same time that it is trying to reconstruct the incomplete image through the
iterative process? To answer this question, we tried to solve a much harder
problem in which the mask is not provided to the model and the model is
agnostic to it. To better understand how a solution could be hypothesized for
this problem, we first imagine that we want to consider all the available
regions in our image that could be potential places to fill in, i.e., we set
the mask in the previous formula 1 to be equal to the incomplete image
$x_{I}$. This is problematic as the model quickly tries to fill in all white
space and quickly reconstructs the incomplete image by doing so. On the other
hand, we can take the inverse problem of the current problem, where the model
tries to just fill in the regions that fragmented contour lives in. Taking
these two at the same time, we came up with a novel loss term for energy
minimization term that helps us remove the need for the mask in the case of
the contour completion problem:

$E(x;x_{I})=\alpha\times\overbrace{\|(x-x_{I})\odot x_{I}\|\
^{2}}^{\text{missing region reconstruction
loss}}+(1-\alpha)\times\overbrace{\left\|(1-x)\odot(1-x_{I})-(1-x_{I})\odot(1-x_{I})\right\|\
^{2}}^{\text{original contour reconstruction regularization term}}$ (2)

In this term, we introduce a linear combination of the two loss terms, where
one focuses on reconstructing the missing regions in the foreground, and one
focuses on avoiding inpainting regions in the background. The logic behind
this is that, if we assume the original image to be representative of the
mask, then the model tries to reconstruct in all white regions (the
foreground), and in the inverse problem we just want to reconstruct the
regions that are already part of the ground truth.

###  2.2 Stopping Criteria

As shown in Figure 2, knowing when to stop iterating to the over-fitted model
is a key to obtaining a completed shape. Therefore, we equipped our model with
a criterion that uses two individual novel terms to know when to stop and
output the result of the network. These two metrics expand the capability of
the generator network beyond what it does currently and achieve a full end-to-
end contour completion model that trains and infers on a single image of
divided contour fragments. These new terms are: reconstruction_score ($\rho$)
and overfit_score ($\omega$).

####  2.2.1 Reconstruction Score

The first score that this paper suggests is the reconstruction score, i. e.,
we have to make sure that the model is trained enough that it can reconstruct
at least the entire set of fragmented contours within the image. This is a
trivial score and to compute the reconstruction_score ($\rho$), we apply a
$k$-dimensional tree (KDTree) nearest-neighbor lookup to find the ratio of
points in the original incomplete image ($x_{0}$). This score ranges from
$[0-100]$.

####  2.2.2 Overfit Score

It is evident that the model overfits the fragmented contours. This is due to
the fact that the error in our loss term is minimized as the $x$ overfits to
$x_{I}$, i. e., replacing $x$ with $x_{I}$ in the loss term would give us
zero. As we hypothesize iterative process also produces the complete image
before it overfits to the incomplete image, we can imagine that at some point
the image is complete ($x_{C}$) and does not need to be fine-tuned any more to
overfit to $x_{I}$. We suggest a new score called overfit_score. overfit_score
determines how much of the reconstructed outcome is over the number of pixels
that are already in the incomplete image ($x_{I}$). To compute the
overfit_score ($\omega$), we apply a $k$-dimensional tree (KDTree) nearest-
neighbor lookup of points in the outcome of the input image and see what
portions of those points are novel and not already in the incomplete image
($x_{I}$). Similar to reconstruction_score, the overfit_score also ranges from
$[0-100]$.

####  2.2.3 Combined Score

To be able to find the best possible set of completed contours, we combine the
two and have a loop that tries to achieve close to full reconstruction and
avoids over-fitting at the same time. This is what we call an "ideal" stopping
point in the contour completion problem. In each run throughout all
iterations, we pick an output of the network that minimizes a dissimilarity
term:

$\delta=\sqrt{(\rho-100)^{2}+(\omega-\gamma)^{2}}$ (3)

where $\delta$ represents our dissimilarity score. The reconstruction_score
and overfit_score are obtainable given network output and the incomplete
image. Ideally, we want to achieve an output image that has a
reconstruction_score equal to 100 and an overfit_score of $\gamma$ which is a
hyperparameter that is dependent on the image and complexity of the shape.
Empirically, we observed that this value is highly correlated with the
distance between gaps that are observed in fragmented contours, i. e., the
larger the gap results in a larger $\gamma$ value. We will discuss this in
more detail in the next section (see Section 3).

Figure 5:  This example shows how different scores change throughout a single
run. All three scores change in the range of $[0,100]$. Our goal is to
maximize reconstruction_score and minimize the overfit_score, but we should
consider that the minimization lower bound is data dependent and is not zero.

For one sample image, we computed the two metrics reconstruction_score and
overfit_score and the combined value of dissimilarity ($\delta$) and showed
how these values change (see Figure 5). Our initial observations show that the
reconstruction_score will increase to 100 quickly for the incomplete image
indicating that the already existing fragments of the contours have been
reconstructed in the output.

However, as mentioned previously, we cannot solely rely on this score since we
also want to minimize the overfitting. Remember that our goal is to produce an
output that: a) preserves the original contours in the incomplete image and b)
fills in the gaps between the fragmented contours. It is evident that
overfit_score decreases throughout an iterative run of our process until it
reaches zero. The dissimilarity will also decrease along with the overfit to a
point, then it will increase, as the model tries to reproduce the incomplete
image. This is where an ideal $\gamma$ value can be picked, i.e., where to
stop when the reconstruction is good but we have not done a full overfit to
the incomplete image. Thus, one should pick the value of $\gamma$ empirically
in the scenario that the ground truth is not available, whereas, assuming that
the ground truth is available, we can easily compute the best $\gamma$ value.
In our experiments, we tried two datasets of images with different gap sizes.
We observed that the best the $\gamma$ for one set of samples is $\sim 5$ (the
set with shorter gaps) while it is $\sim 23$ for samples from the other set,
i. e, the set with longer gaps (see Figure 6 for some completed examples).

|  |  |  |  |  |  |
---|---|---|---|---|---|---|---
|  |  |  |  |  |  |
|  |  |  |  |  |  |
Figure 6: Evolutionary process of the deep structure prior. The right column
shows the incomplete shapes given to the model and the rest of the columns
show how the model is overfitting gradually to produce the incomplete shapes.
In each column, we are showing an intermediate iteration of this process. The
loss-term setup enables our pipeline to let the completed image appears during
this iterative process.

##  3 Experiments and Results

Performing unsupervised contour completion is a difficult task to benchmark as
one can never know what fragments exactly are connected to each other in a
real-world scenario. This makes the problem of contour completion a hard
problem to solve. In this paper, we tried to create artificial shapes that are
occluded by some masks and then tried to see if our model can regenerate the
missing pieces and glue those divided contours together. To demonstrate our
model’s behavior, we will conduct experiments on datasets created for this
task and will report on them in this section. To compare network results in
different settings, we will use pixel-wise Mean Squared Error (MSE) and
Intersection over Union (IoU) between the produced result of the network and
unmasked ground truth data and the reconstructed image on black pixels (where
contours live).

###  3.1 Data

We prepared two datasets, one labeled “Simple" and one “Complex", in
accordance with the number of gaps in each shape. Both datasets contain nine
different categories of shapes. In order to generate the Complex dataset, we
used FlatShapeNet [32] which is a dataset for the educational game Ariga. The
dataset includes the following categories: Circle, Kite, Parallelogram,
Rectangle, Rhombus, Square, Trapezoid, Triangle and Overlap. The “overlap"
category contains images that are made as a mixture of two shapes that are
overlapping from the previous categories. These are some standard shapes with
a few gaps in simple dataset, while the complex dataset has some hand-drawn
shapes with fragmented lines and more gaps that produce more variety in
general. For each instance, a ground truth image is available for comparison.
Most of our experiments have been conducted using the complex dataset in order
to evaluate the generalization of our approach. For the analysis of how
$\gamma$ values should be set for each shape, we used the simple dataset as a
reference.

###  3.2 Evaluation

In this section, we compare our model to the original Deep Image Prior (DIP)
[29] inpainting model. DIP’s inpainting module accepts a degraded image and a
binary mask corresponding to that image. In order to make a fair comparison,
instead of providing a binary mask, we used the incomplete images both as
input and as a mask in order to see whether it can produce a result similar to
ours.

For DIP, we run the iterative process for a maximum number of 2500 iterations
with the U-net backbone. We used the exact same architecture and setting in
our model for a fair comparison. Using our ground truth dataset images, we
calculate the MSE loss between the network output and ground truth during each
iteration instead of relying on our stopping mechanism described in the
previous section. We then store the output with minimal loss throughout all
the iterations. Finally, we select the best output among all iterations,
report the MSE and IoU with the ground truth, and save the iteration number
which resulted in the lowest MSE. Table 1 compares the results that are
obtained using the DIP method, the DSP method (ours), and the difference
between raw images and the ground truth. We have presented the average MSE-
loss, average IoU, and the average number of iterations for the best output
for different methods. As can be seen from the table, our model improves both
MSE and IoU between the incomplete image and ground truth in fewer iterations.
The DIP method can neither generate a better result than the raw image nor
provide stopping criteria to prevent overfitting. We provide a more detailed
analysis of this result in Figure 7. As results show, our algorithm not only
provides a much faster convergence but also consistently provides a better-
completed image (consistently less MSE loss and better IoU), whereas it is
challenging for the DIP method to accomplish better results without a guiding
mask.

|  |
---|---|---
(a) | (b) | (c)
Figure 7: In this Figure, we compare the completed images from our algorithm, DSP, (shown in green) with the best obtained completed images from the DIP method (shown in red). We compare MSE loss between the degraded raw images that these algorithms started with (shown in blue) (a) Mean Squared Error Loss: we clearly see that for almost all images, DSP (green) achieves a lower MSE than the incomplete images (blue) whereas, the DIP completed images either do not improve the MSE or even worsen that for the incomplete images. Note that, the MSE is computed to an available ground truth image hidden from our methods (the lower is better). (b) Intersection Over Union: here, we are looking at the IoU metric that specifies the amount of intersection over the union between the obtained images and the ground truth data. Again, we see that DSP produces images that are much closer to the ground truth (in most cases) whereas the DIP can not achieve a similar result. While we see few DIP completed images produce a better IoU than the degraded images (in terms of IoU), most of them are worse than the starting image (the higher is better). (c) The number of iterations that are needed for each algorithm to obtain its best results. Here, we see that DSP can quickly produce the best outcome with the least MSE loss whereas the DIP algorithm’s best results are when we run the iterative process for more iterations (the lower is better).  Table 1: Average MSE and IoU values between the incomplete (Raw) images, the output of DIP and DSP methods, and ground truth for each image are provided in this table. Method | MSE | IoU | Iterations | Time (s)
---|---|---|---|---
Raw | 829.01 | 0.65 | 0 | 0
DIP | 2027.52 | 0.29 | 2013 | 54.68
DSP (Ours) | 490.84 | 0.74 | 359 | 9.55

###  3.3 Correlation of $\gamma$ with the Gap Size

To better understand the $\gamma$ parameter of our combined score, we
conducted the following experiment. A total of 12000 samples were obtained by
merging all of our images from the two datasets, simple and complex. As we
have access to the ground truth for each degraded image in the combined
dataset, we can easily calculate reconstruction_score and overfit_score for
each degraded-ground truth pair. As expected, we obtain a reconstruction_score
of 100 for all samples, but the overfit_score varies among them. Intuitively,
we hypothesized that an optimal value of overfit score should be intertwined
with the total area of gaps. To test this hypothesis, we did the following
experiment. We first define a function $\phi(x)$ which takes a binary, black
and white image $x$ and returns the number of black pixels in it. Then we
define a gap term as follows:

$gap=\frac{\phi(x_{gt})-\phi(x_{I})}{\phi(x_{gt})}$ (4)

where $x_{I}$ is the incomplete image and $x_{gt}$ is the ground truth. In
this case, gap indicates the total area of the gap with respect to the whole
shape. We found out that this term and the best result have a correlation of
$\mathbf{97.43\%}$. This indicates that the value of $\gamma$ is highly
correlated with the gap size, that is something expected in a way.

###  3.4 Effect of $\alpha$

We conducted additional experiments concerning how $\alpha$ affects the
quality of reconstruction. In the previous section, we defined Equation 2 as
the loss term that guides our iterative process. The term $\alpha$ specifies
the amount of emphasis the model should place on reconstructing missing
regions, rather than filling in fragmented contours. A lower $\alpha$
indicates a better grouping quality, as shown in Equation 2. However, we will
not achieve completion if we remove the first term completely from the loss by
setting $\alpha=0$. Therefore, the first term should be kept, but its weight
should be very low in order to achieve a good completion. On the other hand,
if we set $\alpha=1$ and omit the second term, we lose the contour completion
regularization term and obtain the same output as a vanilla deep image prior,
which does not complete shapes.

Table 2:  For this experiment, we ran the model over a subset of complex
dataset with 500 incomplete images at various levels of alpha for 250
iterations. After the image completion is done, we compared the evaluation
metrics between the completed image and the ground truth to examine the
performance of the model for different values of alpha.
Alpha | MSE | IoU | Iterations | Time (s)
---|---|---|---|---
0 | 17240.44 | 0.04 | 0 | 0
0.05 | 619.82 | 0.71 | 221 | 7.75
0.1 | 456.77 | 0.76 | 210 | 7.35
0.15 | 456.52 | 0.75 | 184 | 6.37
0.2 | 485.53 | 0.74 | 157 | 5.44
0.25 | 527.35 | 0.73 | 151 | 5.25
0.3 | 551.23 | 0.72 | 151 | 5.25
0.35 | 602.57 | 0.71 | 155 | 5.31
0.4 | 644.36 | 0.69 | 160 | 5.34
0.45 | 682.33 | 0.68 | 172 | 5.77
0.5 | 749.29 | 0.66 | 183 | 6.13
0.55 | 825.89 | 0.63 | 197 | 6.80
0.6 | 906.45 | 0.60 | 206 | 7.10
0.65 | 996.34 | 0.57 | 222 | 7.70
0.7 | 1132.19 | 0.52 | 228 | 7.91
0.75 | 1294.25 | 0.48 | 228 | 7.92
0.8 | 1546.86 | 0.43 | 225 | 7.78
0.85 | 2111.38 | 0.36 | 216 | 7.40
0.9 | 4031.41 | 0.29 | 185 | 6.32
0.95 | 7772.83 | 0.16 | 107 | 3.70
1 | 12258.55 | 0.06 | 11 | 0.36
Raw | 843.23 | 0.65 | 0 | 0

###  3.5 Effect of Receptive Field Size

To better understand the effect of receptive field size on our algorithm, we
test the following hypothesis: can models with bigger receptive field size
complete shapes with bigger gaps? In Table 3, we report showing the results of
this experiment. As we can see, the bigger the receptive field size, the more
complete shapes we can reconstruct using DSP.

Table 3: In this table, we show the effect of the receptive filter size on our algorithm’s capability to fill in bigger gap sizes. The numbers in this table are showing the percentage of the time that DIP was successful to complete shapes with each gap size and corresponding receptive field size. As predicted, the bigger the filter size, the more successful the algorithm is in filling in the gaps.  Receptive | Gap Size
---|---
Filter size | 8 | 10 | 12 | 15
3 | 66.66% | 56.0% | 26.13 % | 20.26%
5 | 85.33% | 66.66% | 54.13% | 26.13%
7 |  85.33% |  76.0 % |  54.66% |  26.93%

##  4 Implementation Details

As shown in Figure 3, we use a model with 5 layers and 128 channels for
downsampling and upsampling convolutions, and 64 channels for skip
convolutions. The upsampling and downsampling modules use $3\times 3$ filters,
while the skip module uses $1\times 1$ filters. In the upsample part of the
network, the nearest neighbor algorithm is used. We used $256\times 256$
images with three channels in all of our experiments. In training, we use the
MSE loss between the degraded image and the output of the network, and we
optimize the loss using the ADAM optimizer and a learning rate equal to 0.01 .
In our experiments, we also used $\alpha=0.15$ as an optimal proportion
coefficient for reconstruction loss.

##  5 Conclusion

In this work, we introduced a novel framework for contour completion using
deep structure priors (DSP). This work offers a novel notion of a maskless
grouping of fragmented contours. In our proposed framework, we introduced a
novel loss metric that does not require a strict definition of the mask.
Instead, it lets the model learn the perceivable illusory contours and
connects those fragmented pieces using a generator network that is solely
trained on just the single incomplete input image. Our model does not require
any pre-training which demonstrates that the convolutional architecture of the
hour-glass model is able to connect disconnected contours. We present an
extended set of experiments that show the capability of our algorithm. We
investigate the effect of each parameter introduced in our algorithm
separately and show how one could possibly achieve the best result for their
problem using this model. In future work, we plan to extend this model and try
to see how it performs with real images. In particular, we want to determine
whether we can inpaint real-world photographs while retaining perceptually
aware scene structures. The importance of shape in perception by deep neural
networks has been highlighted in many adversarial examples to appearance-based
networks [33]. The outcome of this work has strong potential to impact the
designing and implementation of models that are robust to such perturbations.

## References

  * [1] Ronald A Rensink and James T Enns.  Early completion of occluded objects.  Vision research, 38(15-16):2489–2505, 1998.
  * [2] Andrew P Witkin and Jay M Tenenbaum.  On the role of structure in vision.  In Human and machine vision, pages 481–543. Elsevier, 1983.
  * [3] David G Lowe.  Visual recognition from spatial correspondence and perceptual organization.  In IJCAI, pages 953–959. Citeseer, 1985.
  * [4] Sudeep Sarkar and Kim L Boyer.  Perceptual organization in computer vision: A review and a proposal for a classificatory structure.  IEEE Transactions on Systems, Man, and Cybernetics, 23(2):382–399, 1993.
  * [5] Jacqueline Goodnow.  Children’s Drawing (The Developing Child).  HarperCollins Publishers, 1980.
  * [6] Morteza Rezanejad.  Medial measures for recognition, mapping and categorization.  McGill University, 2020.
  * [7] Alex Levinshtein, Cristian Sminchisescu, and Sven Dickinson.  Multiscale symmetric part detection and grouping.  International journal of computer vision, 104(2):117–134, 2013\.
  * [8] Tom Lee, Sanja Fidler, and Sven Dickinson.  Learning to combine mid-level cues for object proposal generation.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1680–1688, 2015.
  * [9] Morteza Rezanejad, Gabriel Downs, John Wilder, Dirk B Walther, Allan Jepson, Sven Dickinson, and Kaleem Siddiqi.  Gestalt-based contour weights improve scene categorization by cnns.  In Conference on Cognitive Computational Neuroscience (CCN 2019), volume 2, 2019.
  * [10] Wallace S Rutkowski.  Shape completion.  Computer graphics and image processing, 9(1):89–101, 1979.
  * [11] Shimon Ullman.  Filling-in the gaps: The shape of subjective contours and a model for their generation.  Biological Cybernetics, 25(1):1–6, 1976.
  * [12] Mike Brady, W Eric L Grimson, and DJ Langridge.  Shape encoding and subjective contours.  In AAAI, pages 15–17, 1980.
  * [13] Berthold KP Horn.  The curve of least energy.  ACM Transactions on Mathematical Software (TOMS), 9(4):441–460, 1983.
  * [14] David Mumford.  Elastica and computer vision.  In Algebraic geometry and its applications, pages 491–506. Springer, 1994.
  * [15] Eitan Sharon, Achi Brandt, and Ronen Basri.  Completion energies and scale.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(10):1117–1131, 2000.
  * [16] Washington Mio, Anuj Srivastava, and Xiuwen Liu.  Contour inferences for image understanding.  International journal of computer vision, 69(1):137–144, 2006.
  * [17] Jiahui Yu, Zhe Lin, Jimei Yang, Xiaohui Shen, Xin Lu, and Thomas S Huang.  Generative image inpainting with contextual attention.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5505–5514, 2018.
  * [18] Omar Elharrouss, Noor Almaadeed, Somaya Al-Maadeed, and Younes Akbari.  Image inpainting: A review.  Neural Processing Letters, 51(2):2007–2028, 2020.
  * [19] Zhen Qin, Qingliang Zeng, Yixin Zong, and Fan Xu.  Image inpainting based on deep learning: A review.  Displays, 69:102028, 2021.
  * [20] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.
  * [21] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  arXiv preprint arXiv:2204.06125, 2022.
  * [22] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S Sara Mahdavi, Rapha Gontijo Lopes, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  arXiv preprint arXiv:2205.11487, 2022.
  * [23] Kurt Koffka.  Perception: an introduction to the gestalt-theorie.  Psychological Bulletin, 19(10):531, 1922.
  * [24] Lance R Williams and David W Jacobs.  Local parallel computation of stochastic completion fields.  In Proceedings CVPR IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 161–168. IEEE, 1996.
  * [25] Lance R Williams and David W Jacobs.  Local parallel computation of stochastic completion fields.  Neural computation, 9(4):859–881, 1997.
  * [26] Morteza Rezanejad, Sidharth Gupta, Chandra Gummaluru, Ryan Marten, John Wilder, Michael Gruninger, and Dirk B. Walther.  Contour-guided image completion with perceptual grouping.  In 32nd British Machine Vision Conference 2021, BMVC 2021, Online, November 22-25, 2021, page 73. BMVA Press, 2021.
  * [27] Charles-Olivier Dufresne Camaro, Morteza Rezanejad, Stavros Tsogkas, Kaleem Siddiqi, and Sven Dickinson.  Appearance shock grammar for fast medial axis extraction from real images.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14382–14391, 2020.
  * [28] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning (still) requires rethinking generalization.  Communications of the ACM, 64(3):107–115, 2021.
  * [29] 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.
  * [30] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks.  Communications of the ACM, 63(11):139–144, 2020.
  * [31] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In International Conference on Medical image computing and computer-assisted intervention, pages 234–241. Springer, 2015.
  * [32] Moch. Galang Rivaldo.  FlatShapeNet, 3 2022.
  * [33] Nicholas Baker, Hongjing Lu, Gennady Erlikhman, and Philip J Kellman.  Local features and global shape information in object classification by deep convolutional neural networks.  Vision research, 172:46–61, 2020.


for any $l\in\llbracket 1,d_{V}\rrbracket$. We divide the proof in the
following key steps. We first show that for fixed $(u,v)\in B$, it holds that

$\lim_{N\to\infty}\mathbb{E}\|\alpha_{l}(\cdot\,;u,v)-\alpha_{l}^{(N)}(\cdot\,;u,v)\|_{L^{2}}=0,$
(51)

for any $l\in\llbracket 1,d_{V}\rrbracket$. By using compactness and applying
the Arzelà-Ascoli theorem, we then show that for $(u,v)\in B$

$\lim_{N\to\infty}\mathbb{E}\|\alpha_{l}(\cdot\,;u,v)-\alpha_{l}^{(N)}(\cdot\,;u,v)\|_{C(\bar{D})}=0,$
(52)

for any $l\in\llbracket 1,d_{V}\rrbracket$. We then use the compactness of $B$
and continuity of the mappings $(u,v)\mapsto\alpha_{\ell}(\cdot\,;u,v)$ and
$(u,v)\mapsto\alpha^{(N)}_{\ell}(\cdot\,;u,v)$ to deduce the result given by
(50). We now focus on establishing (51). Since $B$ is bounded, there exists a
constant $M>0$ such that,

$\sup_{(u,v)\in B}\|u\|_{L^{\infty}}+\|v\|_{L^{\infty}}\leq M.$

Therefore, we have

$\sup_{(u,v)\in
B}\max\\{\|f\|,\|g_{1}\|,\dots,\|g_{m}\|\\}\leq\max\left\\{\text{exp}\big{(}RM^{2}\big{)},M|V|\text{exp}\big{(}RM^{2}\big{)}\right\\}\coloneqq
J,$

where $\|\cdot\|=\|\cdot\|_{C(\bar{D}\times\bar{E})}$. Clearly, it holds that

$\sup_{(u,v)\in
B}\max\\{\|a\|_{L^{2}},\|a^{(N)}\|_{L^{2}}\\}\leq|D|^{1/2}|E|J.$

Notice that, since $|\langle Qu(x),Kv(s)\rangle|\leq RM^{2}$, we have
$f(x,y)\geq\text{exp}\big{(}-RM^{2}\big{)}$. It follows that

$\inf_{(u,v)\in
B}\min\\{\|a\|_{L^{2}},\|a^{(N)}\|_{L^{2}}\\}\geq|D|^{1/2}|E|\text{exp}\big{(}-RM^{2}\big{)}\coloneqq|D|^{1/2}|E|I>0.$

Similarly,

$\sup_{(u,v)\in
B}\max_{l\in[d_{K}]}\\{\|b_{l}\|_{L^{2}},\|b_{l}^{(N)}\|_{L^{2}}\\}\leq|D|^{1/2}|E|J.$

Applying Lemma 27, we find

$\displaystyle\mathbb{E}\left\|\frac{b_{l}}{a}-\frac{b_{l}^{(N)}}{a^{(N)}}\right\|_{L^{2}}$
$\displaystyle\leq\mathbb{E}\frac{\|a^{(N)}\|_{L^{2}}\|b_{l}-b_{l}^{(N)}\|_{L^{2}}+\|b_{l}^{(N)}\|_{L^{2}}\|a-a^{(N)}\|_{L^{2}}}{\|a^{(N)}\|_{L^{2}}\|a\|_{L^{2}}}$
(53a) $\displaystyle\leq\frac{2J^{2}}{I^{2}}N^{-1/2}.$ (53b)

Setting $\alpha_{l}=b_{l}/a$ and $\alpha_{l}^{(N)}=b_{l}^{(N)}/a^{(N)}$, from
(53a) we deduce that for $(u,v)\in B$ it holds that

$\lim_{N\to\infty}\mathbb{E}\|\alpha_{l}(\cdot\,;u,v)-\alpha_{l}^{(N)}(\cdot\,;u,v)\|_{L^{2}}=0,$
(54)

for any $l\in\llbracket 1,d_{V}\rrbracket$. We now proceed to the second step
of the proof, i.e. showing that (52) holds. Using similar reasoning as before,
we notice that

$\displaystyle\inf_{(u,v)\in B}$
$\displaystyle\min\\{\|a\|_{C(\bar{D})},\|a^{(N)}\|_{C(\bar{D})}\\}\geq|E|I,$
(55a) $\displaystyle\sup_{(u,v)\in B}$
$\displaystyle\max_{l\in[m]}\\{\|b_{l}\|_{C(\bar{D})},\|b_{l}^{(N)}\|_{C(\bar{D})}\\}\leq|E|J,$
(55b)

hence the sequence $\\{\alpha_{l}^{(N)}\\}$ is uniformly bounded in $N$. Now,
for fixed $(u,v)\in B$ the sequence $\\{\alpha_{l}^{(N)}(\cdot\,;u,v)\\}$ is
also uniformly equicontinuous with probability 1 over the choice
$\\{y_{j}\\}_{j=1}^{N}\sim U(\bar{D})$. Indeed, we note that

$\displaystyle\left|\frac{b_{l}^{(N)}(r)}{a^{(N)}(r)}-\frac{b_{l}^{(N)}(t)}{a^{(N)}(t)}\right|$
$\displaystyle=\left|\frac{\sum_{j=1}^{N}g_{l}(r,y_{j})}{\sum_{k=1}^{N}f(r,y_{k})}-\frac{\sum_{j=1}^{N}g_{l}(t,y_{j})}{\sum_{k=1}^{N}f(t,y_{k})}\right|$
(56a)
$\displaystyle\leq\frac{1}{N^{2}I}\left|\sum_{j,n}g_{l}(r,y_{j})f(t,y_{n})-g_{l}(t,y_{j})f(r,y_{n})\right|$
(56b)
$\displaystyle\leq\frac{J}{N^{2}I}\sum_{j,n}\bigl{(}\bigl{|}g_{l}(r,y_{j})-g_{l}(t,y_{j})\bigr{|}+\bigl{|}f(t,y_{n})-f(r,y_{n})\bigr{|}\bigr{)}.$
(56c)

The result then follows from the uniform continuity of $f$ and $g_{l}$ in
their first arguments, due to the compactness of $\bar{D}$. Therefore, since
$\bar{D}\subset\mathbbm{R}^{d}$ is compact, by the Arzelà–Ascoli theorem there
exists a subsequence of indices $(N_{k})_{k\in\mathbbm{N}}$ such that
$\alpha_{l}^{(N_{k})}$ converges in $C(\bar{D})$ to some
$\alpha_{l}^{(\infty)}$. Since,

$\mathbb{E}\|\alpha_{l}^{(\infty)}-\alpha_{l}^{(N_{k})}\|_{L^{2}}\leq|D|^{1/2}\mathbb{E}\|\alpha_{l}^{(\infty)}-\alpha_{l}^{(N_{k})}\|_{C(\bar{D})},$

by uniqueness of limits, it is readily observed that
$\alpha_{l}^{(\infty)}=\alpha_{l}$. Therefore, since the limit is independent
of the subsequence, for fixed $(u,v)\in B$ it holds that

$\lim_{N\to\infty}\mathbb{E}\|\alpha_{l}(\cdot\,;u,v)-\alpha_{l}^{(N)}(\cdot\,;u,v)\|_{C(\bar{D})}=0,$

for any $l\in\llbracket 1,d_{V}\rrbracket$. We now turn our attention to
establishing (50). By reasoning as before and by using the continuity of the
exponential and of the inner product on the product space, it is
straightforward to show that as mappings of the form $\alpha_{l}:B\to
C(\bar{D};\mathbbm{R}^{d_{V}})$ and $\alpha_{l}^{(N)}:B\to
C(\bar{D};\mathbbm{R}^{d_{V}})$ where $B$ is compact, $\alpha_{l}$ and
$\alpha_{l}^{(N)}$ are continuous and hence the sequence
$\\{\alpha_{l}^{(N)}\\}$ is uniformly equicontinuous. Therefore, we can find
moduli of continuity $\omega_{1},\omega_{2}$ such that

$\displaystyle\|\alpha_{l}(u,v)-\alpha_{l}(\widetilde{u},\widetilde{v})\|_{C(\bar{D})}$
$\displaystyle\leq\omega_{1}\big{(}\|(u,v)-(\widetilde{u},\widetilde{v})\|_{C(\bar{D})\times
C(\bar{E})}\big{)},$
$\displaystyle\|\alpha_{l}^{(N)}(u,v)-\alpha_{l}^{(N)}(\widetilde{u},\widetilde{v})\|_{C(\bar{D})}$
$\displaystyle\leq\omega_{2}\big{(}\|(u,v)-(\widetilde{u},\widetilde{v})\|_{C(\bar{D})\times
C(\bar{E})}\big{)}$

for any $(u,v),(\widetilde{u},\widetilde{v})\in B$ and $N\in\mathbb{N}$. Fix
$\epsilon>0$. Since $B$ is compact, we can find a number
$L=L(\epsilon)\in\mathbb{N}$ and functions $\phi_{1},\dots,\phi_{L}\in B$ such
that, for any $(u,v)\in B$, there exists $j\in\llbracket 1,L\rrbracket$ such
that

$\|(u,v)-\phi_{j}\|_{C(\bar{D})\times C(\bar{E})}<\epsilon.$

Furthermore, we can find a number $S=S(\epsilon)\in\mathbb{N}$ such that, for
any $j\in\llbracket 1,L\rrbracket$, we have, for all $N\geq S$,

$\mathbb{E}\|\alpha_{l}(\phi_{j})-\alpha_{l}^{(N)}(\phi_{j})\|_{C(\bar{D})}<\epsilon.$

It follows by triangle inequality that

$\displaystyle\mathbb{E}\|\alpha_{l}(u,v)-\alpha_{l}^{(N)}(u,v)\|_{C(\bar{D})}$
$\displaystyle\leq\mathbb{E}\|\alpha_{l}(u,v)-\alpha_{l}(\phi_{j})\|_{C(\bar{D})}+\mathbb{E}\|\alpha_{l}(\phi_{j})-\alpha_{l}^{(N)}(u,v)\|_{C(\bar{D})}$
$\displaystyle\leq|D|\omega_{1}(\epsilon)+\mathbb{E}\|\alpha_{l}(\phi_{j})-\alpha_{l}^{(N)}(\phi_{j})\|_{C(\bar{D})}+\mathbb{E}\|\alpha_{l}^{(N)}(\phi_{j})-\alpha_{l}^{(N)}(u,v)\|_{C(\bar{D})}$
$\displaystyle\leq|E|\omega_{1}(\epsilon)+\epsilon+|E|\omega_{2}(\epsilon).$

Therefore the result follows since our argument is uniform over all
$l\in\llbracket 1,d_{V}\rrbracket$.

##  Appendix B Transformer Neural Operators: The Discrete Setting

We describe how the transformer neural operators described in Section 4 are
implemented in the discrete setting. Namely, in practice we will have access
to evaluations of the input function
$u\in\mathcal{U}\bigl{(}D;\mathbbm{R}^{d_{u}}\bigr{)}$ at a finite set of $N$
discretization points $\\{x_{i}\\}_{i=1}^{N}\subset D$. To highlight how the
neural operator methodology is applied in practical settings it is useful,
abusing notation, to view the input to the neural operators as
$u\in\mathbbm{R}^{N\times d_{u}}$. In order to distinguish between functions
in $\mathcal{U}\bigl{(}D;\mathbbm{R}^{d_{u}}\bigr{)}$, and discrete
representations of these functions at a finite set of grid points, in this
section we use different fonts for a function
$\mathsf{u}\in\mathcal{U}\bigl{(}D;\mathbbm{R}^{d_{u}}\bigr{)}$ and its
discrete analogue $u\in\mathbbm{R}^{N\times d_{u}}$. We highlight that in
practice, it is of interest to apply approximations of the attention operators
$\mathsf{A}$ and $\mathsf{A}_{\mathsf{P}}$ defined on the continuum, to
$u\in\mathbbm{R}^{N\times d_{u}}$. Through an abuse of notation, we will write
$\mathsf{A}_{\mathord{\color[rgb]{0.67,0.67,0.67}\bullet}}(u)$ to denote the
finite-dimensional approximation of
$\mathsf{A}_{\mathord{\color[rgb]{0.67,0.67,0.67}\bullet}}$ acting on
matrices, and similarly for $\mathsf{E}_{L},\mathsf{F}_{\textrm{NN}}$ and
$\mathsf{F}_{\textrm{LN}}.$

In Subsection B.1 we describe the transformer neural operator in the discrete
setting, in Subsection B.2 the vision transformer neural operator and in
Subsection B.3 the Fourier attention neural operator.

###  B.1 Transformer Neural Operator

In this section, we describe how the transformer neural operator from
Subsection 4.2 is implemented in the discrete setting. The input to the model
is therefore a tensor $u\in\mathbbm{R}^{N\times d_{u}}$, which is then
concatenated with the discretization points $\\{x_{i}\\}_{i=1}^{N}\subset D$,
to form the tensor $u_{\textrm{in}}\in\mathbbm{R}^{N\times(d_{u}+d)}$. The
learnable linear transformation
$W_{\textrm{in}}^{\top}\in\mathbbm{R}^{(d_{u}+d)\times d_{\textrm{model}}}$
then acts on $u_{\textrm{in}}$ to yield

$v^{(0)}\coloneqq u_{\textrm{in}}W_{\textrm{in}}^{\top},$

which is then fed through the transformer encoder. In practice we solve the
recurrence relation in (10) on a finite set of $N$ grid points that arise
naturally from the discrete input $u_{\textrm{in}}$. The multi-head attention
operator $\mathsf{A}_{\textrm{MultiHead}}$ is defined by the application of
the linear transformation
$W_{\textrm{MultiHead}}^{\top}\in\mathbbm{R}^{Hd_{K}\times
d_{\textrm{model}}}$ to the concatenation of $H\in\mathbbm{N}$ self-attention
operations. The concatenation of the outputs of the $H\in\mathbbm{N}$ self-
attention operations results in a $\mathbbm{R}^{N\times Hd_{K}}$ tensor, so
that

$\mathsf{A}_{\textrm{MultiHead}}(v)\coloneqq\bigl{(}\mathsf{A}(v;Q_{1},K_{1},V_{1}),\ldots,\mathsf{A}(v;Q_{H},K_{H},V_{H})\bigr{)}{W}_{\textrm{MultiHead}}^{\top}\in\mathbbm{R}^{N\times
d_{\textrm{model}}},$ (57)

for any $v\in\mathbbm{R}^{N\times d_{\textrm{model}}}$. We recall that the
self-attention operator in question, $\mathsf{A}$, is defined in Definition 5
for functions. In the discrete setting, where $v\in\mathbbm{R}^{N\times
d_{\textrm{model}}}$, we compute the expectation and the integral arising from
the normalization constant using the following trapezoidal approximations:

$\mathsf{A}(v)_{j}:=\frac{1}{2}\sum_{k=2}^{N}\Bigl{(}V{v_{k}}\cdot
p(k;v,j)+V{v_{k-1}}\cdot p(k-1;v,j)\Bigr{)}\cdot\Delta x_{k},$ (58)

for any $j=1,\ldots,N$, with

$p(k;v,j)\approx\frac{\exp\Bigl{(}\bigl{\langle}Q{v_{j}},Kv_{k}\bigr{\rangle}_{\mathbbm{R}^{d_{\textrm{\scalebox{0.7}{$K$}}}}}\Bigr{)}}{\frac{1}{2}\sum_{\ell=2}^{N}\Bigl{(}\exp\bigl{(}\bigl{\langle}Q{v_{j}},Kv_{\ell}\bigr{\rangle}_{\mathbbm{R}^{d_{\textrm{\scalebox{0.7}{$K$}}}}}\bigr{)}+\exp\bigl{(}\bigl{\langle}Q{v_{j}},Kv_{\ell-1}\bigr{\rangle}_{\mathbbm{R}^{d_{\textrm{\scalebox{0.7}{$K$}}}}}\bigr{)}\Bigr{)}\Delta
x_{\ell}},$ (59)

where by $u_{\ell}$ we have denoted the $\ell$’th row of the matrix
$v\in\mathbbm{R}^{N\times d_{\textrm{model}}}$, and similarly for
$\mathsf{A}(v)_{\ell}$. In equations (58) and (59) $\Delta x_{k}$ denotes

$\Delta x_{k}\coloneqq\prod_{i=1}^{d}|(x_{k})_{i}-(x_{k-1})_{i}|,$

for $k=2,\ldots,N$, where $(x_{k})_{i}$ is the $i$’th component of the vector
$x_{k}$. This trapezoidal approximation allows for a mathematically consistent
implementation of attention for irregularly sampled data, as demonstrated in
Section 6.

The linear transformations
$W_{1}^{\top},W_{2}^{\top}\in\mathbbm{R}^{d_{\textrm{model}}\times
d_{\textrm{model}}}$ are applied pointwise. It is also straightforward to
apply the definitions for $\mathsf{F}_{\textrm{LayerNorm}}$ in (16) and
$\mathsf{F}_{\textrm{NN}}$ in (18) to the finite representation of $v$ as both
involve pointwise linear transformations. We observe that the recurrence
relation (10) is compatible with varying domain discretization lengths $N$,
and will produce an output $v^{(L)}$ of dimension matching the input
$v^{(0)}$. The resulting tensor $v^{(L)}\in\mathbbm{R}^{N\times
d_{\textrm{model}}}$ is then projected to the output dimension by applying the
learnable linear transformation
$W_{\textrm{out}}^{\top}\in\mathbbm{R}^{d_{\textrm{model}}\times d_{z}}$, so
that the output of the architecture is defined as

$z\coloneqq
v^{(L)}W_{\textrm{out}}^{\top}\in\mathbbm{R}^{d_{\textrm{model}}\times
d_{z}}.$

###  B.2 Vision Transformer Neural Operator

In this section, we describe how the transformer neural operator from
Subsection 4.3 is implemented in the discrete setting. In practice, we will
have access to a discretization of the domain $D$ containing $N$ points and
evaluations of the function $\mathsf{u}\in\mathcal{U}(D;\mathbbm{R}^{d_{u}})$
at these points; the resolution of the input will be determined by
$n_{1}\times\ldots\times n_{d}=N$. The input to the model will therefore be a
tensor $u\in\mathbbm{R}^{n_{1}\times\ldots\times n_{d}\times d_{u}}$. The
input $u\in\mathbbm{R}^{n_{1}\times\ldots\times n_{d}\times d_{u}}$ is first
concatenated with the discretization points $\\{x_{i}\\}_{i=1}^{N}\subset D$,
to form the tensor $u_{\textrm{in}}\in\mathbbm{R}^{n_{1}\times\ldots\times
n_{d}\times(d_{u}+d)}$. Denoting by $p_{1}\times\ldots\times p_{d}$ the
resolution of each patch, application of the reshaping operator
$\mathsf{S}_{\textrm{reshape}}$ results in

$\mathsf{S}_{\textrm{reshape}}\bigl{(}u_{\textrm{in}}\bigr{)}\in\mathbbm{R}^{P\times
p_{1}\times\ldots\times p_{d}\times(d_{u}+d)}.$

Following Definition 20 and the subsequent discussion, the nonlocal linear
operator $\mathsf{W}_{\textrm{in}}$ is implemented as

$\mathsf{W}_{\textrm{in}}(\theta){{u}}\coloneqq\mathcal{F}^{-1}\Bigl{(}R_{\mathsf{W}_{\textrm{in}}}(\theta)\cdot(\mathcal{F}{u})\Bigr{)},$
(60)

for any $u\in\mathbbm{R}^{P\times p_{1}\times\ldots\times
p_{d}\times(d_{u}+d)}$, where we have made explicit the dependence on
$\theta\in\Theta$ to highlight the learnable components in the implementation.
The FFT is computed on the $p_{1}\times\ldots\times p_{d}$ dimensions so that
the resulting tensor is of the form $\mathcal{F}{u}\in\mathbbm{C}^{P\times
p_{1}\times\ldots\times p_{d}\times(d_{u}+d)}$. Since ${u}$ is convolved with
a function that possess only $\bigl{|}Z_{k_{\textrm{max}}}\bigr{|}$ Fourier
modes, the higher Fourier modes may be truncated so that one may consider
$\mathcal{F}{u}\in\mathbbm{C}^{P\times 2k_{\textrm{max},1}\times\ldots\times
2k_{\textrm{max},d}\times(d_{u}+d)}$. The learnable tensor is
$R_{\mathsf{W}_{\textrm{in}}}\in\mathbbm{C}^{2k_{\textrm{max},1}\times\ldots\times
2k_{\textrm{max},d}\times d_{\textrm{model}}\times(d_{u}+d)}$ and the
operation in Fourier space is defined as

$\Bigl{(}R\cdot\bigl{(}\mathcal{F}{u}\bigr{)}\Bigr{)}_{p,i_{1},\ldots,i_{d},\ell}=\sum_{k=1}^{d_{u}+d}R_{p,i_{1},\ldots,i_{d},\ell,k}\bigl{(}\mathcal{F}{u}\bigr{)}_{p,i_{1},\ldots,i_{d},k},$
(61)

for $p\in\llbracket 1,P\rrbracket,\,1\leq i_{j}\leq
2k_{\textrm{max},j},\,1\leq\ell\leq d_{\textrm{model}}$. The inverse FFT is
then applied along the dimensions
$2k_{\textrm{max},1},\ldots,2k_{\textrm{max},d}$. The resulting tensor defined
as ${v}^{(0)}\in\mathbbm{R}^{{P\times p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}}$ is then fed through the transformer encoder
$\mathsf{E}_{L}:\mathbbm{R}^{{P\times p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}}\to\mathbbm{R}^{{P\times p_{1}\times\ldots\times
p_{d}\times d_{\textrm{model}}}}$.

The multi-head attention is based on the self-attention operator acting on
functions from Definition 14. While the expectation is computed with respect
to a probability measure on the patch sequence, hence inducing a discrete
probability mass function, the discretization of the domain introduces the
need to approximate the $L^{2}$ inner product appearing in Definition 13. We
resort to an approximation of the integral given by

$\displaystyle\big{\langle}\mathsf{Q}_{h}{\mathsf{v}}(j),\mathsf{K}_{h}{\mathsf{v}}(k)\big{\rangle}_{L^{2}(D^{\prime},\mathbb{R}^{d_{\textrm{\scalebox{0.7}{$K$}}}})}$
$\displaystyle=\int_{D^{\prime}}\bigl{(}\mathsf{Q}_{h}{\mathsf{v}}(j)\bigr{)}(x)\cdot\bigl{(}\mathsf{K}{\mathsf{v}}(k)\bigr{)}(x)\,\mathrm{d}x$
(62a) $\displaystyle\approx\sum_{x_{i}\in D^{\prime}}\Delta
x_{i}\cdot\bigl{(}\mathsf{Q}_{h}{\mathsf{v}}(j)\bigr{)}(x_{i})\cdot\bigl{(}\mathsf{K}_{h}{\mathsf{v}}(k)\bigr{)}(x_{i})$
(62b)

where we have denoted by $\Delta x_{i}$ the volume of the $i$th cell. We
recall that in this case the linear operators
$\mathsf{Q}_{h},\mathsf{K}_{h},\mathsf{V}_{h}$ are pointwise local operators
hence they admit finite dimensional representations
$Q_{h}\in\mathbbm{R}^{d_{K}\times
d_{\textrm{model}}},K_{h}\in\mathbbm{R}^{d_{K}\times
d_{\textrm{model}}},V_{h}\in\mathbbm{R}^{d_{K}\times d_{\textrm{model}}}$, for
$h=1,\ldots,H$. In the case of uniform patching and uniform discretization of
the domain of size $s^{d}=N$, which is the setting we experiment with, the
approximation reduces to the approximation of the integral of the form

$\big{\langle}\mathsf{Q}_{h}{\mathsf{v}}(j),\mathsf{K}_{h}{\mathsf{v}}(k)\big{\rangle}_{L^{2}(D^{\prime},\mathbb{R}^{d_{\textrm{\scalebox{0.7}{$K$}}}})}\approx\frac{1}{N}\sum_{i_{1},\ldots,i_{d}=1}^{s}\sum_{\ell=1}^{d_{K}}\bigl{(}{v}Q_{h}^{\top}\bigr{)}_{j\times
i_{1}\times\ldots\times
i_{d}\times\ell}\bigl{(}{v}K_{h}^{\top}\bigr{)}_{k\times
i_{1}\times\ldots\times i_{d}\times\ell}.$ (63)

The multi-head attention operator is thus defined by the application of the
linear transformation
$W_{\textrm{MultiHead}}^{\top}\in\mathbbm{R}^{Hd_{K}\times
d_{\textrm{model}}}$ to the concatenation of $H\in\mathbbm{N}$ self-attention
operations defined by the approximations above. The concatenation of the
outputs of the $H\in\mathbbm{N}$ self-attention operations results in a
$\mathbbm{R}^{P\times p_{1}\times\ldots\times p_{d}\times Hd_{K}}$ tensor, so
that

$\mathsf{A}_{\textrm{MultiHead}}(v)\coloneqq\bigl{(}\mathsf{A}_{\mathsf{P}}(v;{Q}_{1},{K}_{1},{V}_{1}),\ldots,\mathsf{A}_{\mathsf{P}}(v;{Q}_{H},{K}_{H},{V}_{H})\bigr{)}W_{\textrm{MultiHead}}^{\top}\in\mathbbm{R}^{P\times
p_{1}\times\ldots\times p_{d}\times d_{\textrm{model}}},$ (64)

for any $v\in\mathbbm{R}^{P\times p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}$. The linear transformations
$W_{1}^{\top},W_{2}^{\top}\in\mathbbm{R}^{d_{\textrm{model}}\times
d_{\textrm{model}}}$ are applied pointwise. The layer normalization operator
is applied as defined in (24) to every point in every patch so that
$\mathsf{F}_{\textrm{LayerNorm}}(v)\in\mathbbm{R}^{P\times
p_{1}\times\ldots\times p_{d}\times d_{\textrm{model}}}$.

The operator $\mathsf{F}_{\textrm{NN}}$ is applied so that
$\mathsf{F}_{\textrm{NN}}(v)\in\mathbbm{R}^{P\times p_{1}\times\ldots\times
p_{d}\times d_{\textrm{model}}}$, for any $v\in\mathbbm{R}^{P\times
p_{1}\times\ldots\times p_{d}\times d_{\textrm{model}}}$. Indeed, in this
finite-dimensional setting $\mathsf{F}_{\textrm{NN}}$ is defined as

$\mathsf{F}_{\textrm{NN}}(v;W_{3},W_{4},b_{1},b_{2})=f\bigl{(}vW_{4}^{\top}+b_{1}\bigr{)}W_{3}^{\top}+b_{2},$
(65)

for any $v\in\mathbbm{R}^{P\times p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}$, where $f$ is a nonlinear activation function
$W_{3}^{\top},W_{4}^{\top}\in\mathbbm{R}^{d_{\textrm{model}}\times
d_{\textrm{model}}}$ are learnable local linear operators and
$b_{1},b_{2}\in\mathbbm{R}^{P\times p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}$ are learnable in the last dimension.

After computing the recurrence for $\mathsf{E}_{L}$ as described in Equation
10, a reshaping operator $\mathsf{S}^{\prime}_{\textrm{reshape}}$ is applied
to the resulting tensor so that

$v\mapsto\mathsf{S}^{\prime}_{\textrm{reshape}}(v)\in\mathbbm{R}^{n_{1}\times\ldots\times
n_{d}\times d_{\textrm{model}}},$ (66)

for any $v\in\mathbbm{R}^{{P\times p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}}$. A pointwise linear transformation
$W_{\textrm{out}}^{\top}\in\mathbbm{R}^{d_{\textrm{model}}\times d_{z}}$ is
then applied according to

$v\mapsto vW_{\textrm{out}}^{\top},$ (67)

for any $v\in\mathbbm{R}^{n_{1}\times\ldots\times n_{d}\times
d_{\textrm{model}}}$. Following Remark 21, an additional convolution in
frequency space may be applied in residual form, where application of the
nonlocal integral operator follows Definition 20 and the subsequent
discussion. To this end, the operation in frequency space is defined similarly
to (61) and the learnable tensor is of the form
$R_{\mathsf{W}_{\textrm{S}}}\in\mathbbm{C}^{k_{\textrm{max},1}\times\ldots\times
k_{\textrm{max},d}\times d_{z}\times d_{z}}.$

###  B.3 Fourier Attention Neural Operator

In this section, we describe how the transformer neural operator from
Subsection 4.4 is implemented in the discrete setting. In practice, we
consider a discretization of the domain $D$ containing $N$ points and
evaluations of the function
$u\in\mathcal{U}\bigl{(}D;\mathbbm{R}^{d_{u}}\bigr{)}$ at these points; the
resolution of the input is defined by $n_{1}\times\ldots\times n_{d}=N$. The
input to the model is hence a tensor $u\in\mathbbm{R}^{n_{1}\times\ldots\times
n_{d}\times d_{u}}$. The input is concatenated with the discretization points
$\\{x_{i}\\}_{i=1}^{N}\subset D$, to form the tensor
$u_{\textrm{in}}\in\mathbbm{R}^{n_{1}\times\ldots\times
n_{d}\times(d_{u}+d)}$. Denoting by $p_{1}\times\ldots\times p_{d}$ the
resolution of each patch, application of the reshaping operator
$\mathsf{S}_{\textrm{reshape}}$ results in

$\mathsf{S}_{\textrm{reshape}}\bigl{(}u_{\textrm{in}}\bigr{)}\in\mathbbm{R}^{P\times
p_{1}\times\ldots\times p_{d}\times(d_{u}+d)}.$

The learnable linear transformation
$W_{\textrm{in}}^{\top}\in\mathbbm{R}^{(d_{u}+d)\times d_{\textrm{model}}}$ is
then applied as a map

$\mathsf{S}_{\textrm{reshape}}\bigl{(}u_{\textrm{in}}\bigr{)}\mapsto\mathsf{S}_{\textrm{reshape}}\bigl{(}u_{\textrm{in}}\bigr{)}W_{\textrm{in}}^{\top}\in\mathbbm{R}^{P\times
p_{1}\times\ldots\times p_{d}\times d_{\textrm{model}}}.$

The resulting tensor $\widetilde{u}^{(0)}$ is then fed through the transformer
encoder

$\mathsf{E}_{L}:\mathbbm{R}^{{P\times p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}}\to\mathbbm{R}^{{P\times p_{1}\times\ldots\times
p_{d}\times d_{\textrm{model}}}}.$

In the recurrence relation that defines the encoder,
$\mathsf{A}_{\textrm{MultiHead}}$ is the multi-head attention operator as
defined in equation (11). In this setting, letting $H\in\mathbbm{N}$ denote
the number of attention heads, the multi-head attention operator is
parametrized by learnable linear integral operators
$\mathsf{Q}_{h}:\mathbbm{R}^{p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}\to\mathbbm{R}^{p_{1}\times\ldots\times p_{d}\times
d_{K}}$, $\mathsf{K}_{h}:\mathbbm{R}^{p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}\to\mathbbm{R}^{p_{1}\times\ldots\times p_{d}\times
d_{K}}$, and $\mathsf{V}_{h}:\mathbbm{R}^{p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}\to\mathbbm{R}^{p_{1}\times\ldots\times p_{d}\times d_{K}}$
for $h=1,\ldots,H$. Following Definition 20 and the subsequent discussion we
implement the linear integral operators as

$\displaystyle\mathsf{Q}_{h}(\theta){{v}}$
$\displaystyle=\mathcal{F}^{-1}\Bigl{(}R_{\mathsf{Q}_{h}}(\theta)\cdot(\mathcal{F}{v})\Bigr{)},$
(68a) $\displaystyle\mathsf{K}_{h}(\theta){v}$
$\displaystyle=\mathcal{F}^{-1}\Bigl{(}R_{\mathsf{K}_{h}}(\theta)\cdot(\mathcal{F}{v})\Bigr{)},$
(68b) $\displaystyle\mathsf{V}_{h}(\theta){v}$
$\displaystyle=\mathcal{F}^{-1}\Bigl{(}R_{\mathsf{V}_{h}}(\theta)\cdot(\mathcal{F}{v})\Bigr{)},$
(68c)

for $h=1,\ldots,H$ and any $v\in\mathbbm{R}^{p_{1}\times\ldots\times
p_{d}\times d_{\textrm{model}}}$, where we have made explicit the dependence
on $\theta\in\Theta$ to highlight the learnable components in the
implementation. In (68) the FFT is computed on the $p_{1}\times\ldots\times
p_{d}$ so that the resulting tensor
$\mathcal{F}{v}\in\mathbbm{C}^{p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}$. Since ${v}$ is a function that possess only
$\bigl{|}Z_{k_{\textrm{max}}}\bigr{|}$ Fourier modes, the higher Fourier modes
may be truncated so that one may consider
$\mathcal{F}{v}\in\mathbbm{C}^{2k_{\textrm{max},1}\times\ldots\times
2k_{\textrm{max},d}\times d_{\textrm{model}}}$. The learnable tensors are of
dimension
$R_{\mathsf{Q}_{h}},R_{\mathsf{K}_{h}},R_{\mathsf{V}_{h}}\in\mathbbm{C}^{2k_{\textrm{max},1}\times\ldots\times
2k_{\textrm{max},d}\times d_{K}\times d_{\textrm{model}}}$ for $h=1,\ldots,H$,
and the operation in Fourier space is defined as

$\Bigl{(}R\cdot\bigl{(}\mathcal{F}{v}\bigr{)}\Bigr{)}_{i_{1},\ldots,i_{d},\ell}=\sum_{k=1}^{d_{\textrm{model}}}R_{i_{1},\ldots,i_{d},\ell,k}\bigl{(}\mathcal{F}{v}\bigr{)}_{i_{1},\ldots,i_{d},k},$
(69)

for any $v\in\mathbbm{R}^{p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}$ and $\,1\leq i_{j}\leq
2k_{\textrm{max},j},\,1\leq\ell\leq d_{K}$. The inverse FFT is computed along
the dimensions $k_{\textrm{max},1},\ldots,k_{\textrm{max},d}$ so that
$\mathsf{Q}_{h}{v},\mathsf{K}_{h}{v},\mathsf{V}_{h}{v}\in\mathbbm{R}^{p_{1}\times\ldots\times
p_{d}\times d_{K}}$ for $h=1,\ldots,H$. We recall that in this case the self-
attention operator $\mathsf{A}$ is defined according to Definition 14. While
the expectation is computed with respect to a probability measure on the patch
sequence, hence inducing a discrete probability mass function, the
discretization of the domain introduces the need to approximate the $L^{2}$
inner product appearing in Definition 13. We resort to an approximation of the
integral given by (62) and (63). The multi-head attention operator is thus
defined by the application of the linear transformation
$W_{\textrm{MultiHead}}^{\top}\in\mathbbm{R}^{Hd_{K}\times
d_{\textrm{model}}}$ to the concatenation of $H\in\mathbbm{N}$ self-attention
operations. The concatenation of the outputs of the $H\in\mathbbm{N}$ self-
attention operations results in a $\mathbbm{R}^{P\times
p_{1}\times\ldots\times p_{d}\times Hd_{K}}$ tensor, so that

$\mathsf{A}_{\textrm{MultiHead}}(v)\coloneqq\bigl{(}\mathsf{A}_{\mathsf{P}}(v;\mathsf{Q}_{1},\mathsf{K}_{1},\mathsf{V}_{1}),\ldots,\mathsf{A}_{\mathsf{P}}(v;\mathsf{Q}_{H},\mathsf{K}_{H},\mathsf{V}_{H})\bigr{)}W_{\textrm{MultiHead}}^{\top}\in\mathbbm{R}^{P\times
p_{1}\times\ldots\times p_{d}\times d_{\textrm{model}}},$ (70)

for any $v\in\mathbbm{R}^{P\times p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}$. The linear transformations
$W_{1}^{\top},W_{2}^{\top}\in\mathbbm{R}^{d_{\textrm{model}}\times
d_{\textrm{model}}}$ are applied pointwise. The layer normalization operator
is applied as defined in (16) to every point in every patch so that
$\mathsf{F}_{\textrm{LayerNorm}}(v)\in\mathbbm{R}^{P\times
p_{1}\times\ldots\times p_{d}\times d_{\textrm{model}}}$. Finally, the
operator $\mathsf{F}_{\textrm{NN}}$ is parametrized and applied as in (65) so
that $\mathsf{F}_{\textrm{NN}}(v)\in\mathbbm{R}^{P\times
p_{1}\times\ldots\times p_{d}\times d_{\textrm{model}}}$, for any
$v\in\mathbbm{R}^{P\times p_{1}\times\ldots\times p_{d}\times
d_{\textrm{model}}}$.

A reshaping operator $\mathsf{S}^{\prime}_{\textrm{reshape}}$ to the tensor
resulting from the transformer encoder iteration as in Equation 66. A
pointwise linear transformation
$W_{\textrm{out}}^{\top}\in\mathbbm{R}^{d_{\textrm{model}}\times d_{z}}$ is
then applied as in Equation 67. Again, following Remark 21, an additional
convolution in frequency space may be applied in residual form, where
application of the nonlocal integral operator follows Definition 20 and the
subsequent discussion. To this end, the operation in frequency space is
defined similarly to (61) and the learnable tensor is of the form
$R_{\mathsf{W}_{\textrm{S}}}\in\mathbbm{C}^{k_{\textrm{max},1}\times\ldots\times
k_{\textrm{max},d}\times d_{z}\times d_{z}}.$

##  Appendix C Complexity of the Transformer Neural Operators

We summarize the expressions for the parameter complexity and evaluation cost
(measured in floating point operations, FLOPS) of the neural operators from
Section 4 and the Fourier neural operator (FNO) from Li et al. (2021). These
are provided in Tables 4 and 5, respectively. In Subsection C.1 and C.2 we
provide further details for the computations of the parameter and evaluation
cost complexities, respectively.

###  C.1 Parameter Complexity

Architecture | Parameter Complexity
---|---
FNO | $(d_{u}+d)\cdot d_{\textrm{FNO}}+2d_{\textrm{FNO}}\cdot d_{\textrm{model}}+d_{\textrm{FNO}}\cdot d_{z}+4\cdot\bigl{(}d^{2}_{\textrm{model}}\cdot k_{\textrm{max}}+d_{\textrm{model}}^{2}\bigr{)}$
Transformer NO | $(d_{u}+d)\cdot d_{\textrm{model}}+d_{\textrm{model}}\cdot d_{z}+6\cdot\bigl{(}6d^{2}_{\textrm{model}}+2d_{\textrm{model}}\bigr{)}$
ViT NO | $(d_{u}+d)\cdot d_{\textrm{model}}\cdot k_{\textrm{max}}+d_{\textrm{model}}\cdot d_{z}+6\cdot\bigl{(}6d^{2}_{\textrm{model}}+2d_{\textrm{model}}\bigr{)}$
FANO | $(d_{u}+d)\cdot d_{\textrm{model}}+d_{\textrm{model}}\cdot d_{z}+6\cdot\bigl{(}3d^{2}_{\textrm{model}}\cdot k_{\textrm{max}}+3d^{2}_{\textrm{model}}+2d_{\textrm{model}}\bigr{)}$
Table 4: Parameter complexity for the three proposed transformer neural
operators, as implemented in practice, compared to the Fourier neural operator
(Li et al., 2021). We note that for our implementations, $d_{\textrm{FNO}}$,
which is the latent dimension of the two-layer lifting and projection MLP in
FNO, is fixed to be $128$. Parameters arising from possible bias terms,
parameters arising from skip connections in FNO, as well as parameters arising
from a final convolution employed for the patching architectures are omitted
for ease of presentation.

###  C.2 Evaluation Cost

We note that a matrix vector product $Wu$ for $W\in\mathbbm{R}^{r\times
r^{\prime}}$ has cost $2rr^{\prime}$. We approximate the cost of computing the
FFT of a vector in $\mathbbm{R}^{r}$ as $5r\log r$ (Hoop et al., 2022). We
approximate the cost of the two-dimensional real FFT, used in implementation,
by $(15/2)\cdot N\log(\sqrt{N})$ where $N$ is the total number of grid points.
Assuming that the grid is of size $s\times s=N$ for $s$ an even integer, 1d
FFTs are first computed for each row. The real FFT requires $s/2$ column 1d
FFTs, hence the $(15/2)\cdot N\log\sqrt{N}$ complexity.

Architecture | Evaluation Cost
---|---
FNO | $\begin{aligned} &2N(d_{u}+d+2d_{\textrm{model}})d_{\textrm{FNO}}+2Nd_{\textrm{FNO}}d_{z}\\\ &+4\bigl{(}15d_{\textrm{model}}N\log(\sqrt{N})+k_{\textrm{max}}\cdot(2d^{2}_{\textrm{model}}-d_{\textrm{model}})\\\ &+2Nd^{2}_{\textrm{model}}\bigr{)}\end{aligned}$
Transformer NO | $\begin{aligned} &2N(d_{u}+d)d_{\textrm{model}}+2Nd_{\textrm{model}}d_{z}+6\bigl{(}8d^{2}_{\textrm{model}}N\\\ &+2N^{2}d_{\textrm{model}}+4d^{2}_{\textrm{model}}N\bigl{)}\end{aligned}$
ViT NO | $\begin{aligned} &(d_{u}+d+d_{\textrm{model}})\cdot 15N\log(\sqrt{N/P})/2\\\ &+Pk_{\textrm{max}}d_{\textrm{model}}\bigl{(}2(d_{u}+d)-1\bigr{)}+2Nd_{\textrm{model}}d_{z}\\\ &+6\Bigl{(}8d^{2}_{\textrm{model}}N+2d_{\textrm{model}}NP+4d^{2}_{\textrm{model}}N\Bigr{)}\\\ &+15d_{z}N\log(\sqrt{N})+k^{\prime}_{\textrm{max}}(2d^{2}_{z}-d_{z})\end{aligned}$
FANO | $\begin{aligned} &2N(d_{u}+d)d_{\textrm{model}}+2Nd_{\textrm{model}}d_{z}\\\ &+6\Bigl{(}45d_{\textrm{model}}N\log(\sqrt{N/P})+3k_{\textrm{max}}P\bigl{(}2d^{2}_{\textrm{model}}-d_{\textrm{model}}\bigr{)}\\\ &+2Nd^{2}_{\textrm{model}}+2d_{\textrm{model}}NP+4Nd^{2}_{\textrm{model}}\Bigr{)}\\\ &+15d_{z}N\log(\sqrt{N})+k^{\prime}_{\textrm{max}}(2d^{2}_{z}-d_{z})\end{aligned}$
Table 5: Evaluation cost (in FLOPS) for the proposed transformer neural
operators, as implemented in practice, compared to FNO (Li et al., 2021). As
done in Kaplan et al. (2020) and for ease of presentation, the additional
evaluation cost arising from nonlinear activations, the softmax operator and
normalizations are omitted. Furthermore, we omit the cost arising from skip
connections. Indeed these do not affect the scaling. We further note that for
our implementations, $d_{\textrm{FNO}}$, which is the latent dimension of the
two-layer lifting and projection MLP in FNO, is fixed to be $128$.

## References

  * Bahdanau et al. (2014) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  _CoRR_ , abs/1409.0473, 2014.
  * Bi et al. (2023) Kaifeng Bi, Lingxi Xie, Hengheng Zhang, Xin Chen, Xiaotao Gu, and Qi Tian.  Accurate medium-range global weather forecasting with 3d neural networks.  _Nature_ , 619:1–6, 07 2023.
  * Cao (2021) Shuhao Cao.  Choose a transformer: Fourier or galerkin.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 24924–24940. Curran Associates, Inc., 2021.
  * Chandler and Kerswell (2013) Gary J. Chandler and Rich R. Kerswell.  Invariant recurrent solutions embedded in a turbulent two-dimensional kolmogorov flow.  _Journal of Fluid Mechanics_ , 722:554–595, 2013.  doi: 10.1017/jfm.2013.122.
  * Chattopadhyay et al. (2022) A. Chattopadhyay, M. Mustafa, P. Hassanzadeh, E. Bach, and K. Kashinath.  Towards physics-inspired data-driven weather forecasting: integrating data assimilation with a deep spatial-transformer-based u-net in a case study with era5.  _Geoscientific Model Development_ , 15(5):2221–2237, 2022.
  * Chen et al. (2017) Long Chen, Hanwang Zhang, Jun Xiao, Liqiang Nie, Jian Shao, Wei Liu, and Tat-Seng Chua.  Sca-cnn: Spatial and channel-wise attention in convolutional networks for image captioning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 5659–5667, 2017.
  * Cheng et al. (2023) Sibo Cheng, César Quilodrán-Casas, Said Ouala, Alban Farchi, Che Liu, Pierre Tandeo, Ronan Fablet, Didier Lucor, Bertrand Iooss, Julien Brajard, Dunhui Xiao, Tijana Janjic, Weiping Ding, Yike Guo, Alberto Carrassi, Marc Bocquet, and Rossella Arcucci.  Machine learning with data assimilation and uncertainty quantification for dynamical systems: A review.  _IEEE/CAA Journal of Automatica Sinica_ , 10(6):1361–1387, 2023.
  * Chung et al. (2014) Junyoung Chung, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio.  Empirical evaluation of gated recurrent neural networks on sequence modeling.  In _Neural Information Processing Systems 2014 Workshop on Deep Learning, December 2014_ , 2014.
  * Dosovitskiy et al. (2021) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_ , 2021.
  * Geshkovski et al. (2023) Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet.  The emergence of clusters in self-attention dynamics.  _arXiv preprint_ , arXiv:2305.05465, 2023.
  * Guibas et al. (2022) John Guibas, Morteza Mardani, Zongyi Li, Andrew Tao, Anima Anandkumar, and Bryan Catanzaro.  Efficient token mixing for transformers via adaptive fourier neural operators.  In _International Conference on Learning Representations_ , 2022.
  * Hao et al. (2023) Zhongkai Hao, Zhengyi Wang, Hang Su, Chengyang Ying, Yinpeng Dong, Songming Liu, Ze Cheng, Jian Song, and Jun Zhu.  Gnot: A general neural operator transformer for operator learning.  In _Proceedings of the 40th International Conference on Machine Learning_ , ICML’23. JMLR.org, 2023.
  * Hayden et al. (2011) Kevin Hayden, Eric Olson, and Edriss S. Titi.  Discrete data assimilation in the lorenz and 2d navier–stokes equations.  _Physica D: Nonlinear Phenomena_ , 240(18):1416–1425, 2011.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber.  Long Short-Term Memory.  _Neural Computation_ , 9(8):1735–1780, 11 1997.
  * Hoop et al. (2022) Maarten V. de Hoop, Daniel Zhengyu Huang, Elizabeth Qian, and Andrew M. Stuart.  The cost-accuracy trade-off in operator learning with neural networks.  _Journal of Machine Learning_ , 1(3):299–341, 2022.  ISSN 2790-2048.
  * Kaplan et al. (2020) Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeff Wu, and Dario Amodei.  Scaling laws for neural language models.  _arXiv preprint_ , arXiv:2001.08361, 2020.
  * Kovachki et al. (2023) Nikola Kovachki, Zongyi Li, Burigede Liu, Kamyar Azizzadenesheli, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar.  Neural operator: Learning maps between function spaces with applications to pdes.  _Journal of Machine Learning Research_ , 24(89):1–97, 2023.
  * Lanthaler et al. (2023) Samuel Lanthaler, Zongyi Li, and Andrew M. Stuart.  The nonlocal neural operator: Universal approximation.  _arXiv preprint_ , arXiv:2304.13221, 2023.
  * Li et al. (2023) Zijie Li, Kazem Meidani, and Amir Barati Farimani.  Transformer for partial differential equations’ operator learning.  _Transactions on Machine Learning Research_ , 2023.  ISSN 2835-8856.
  * Li et al. (2021) Zongyi Li, Nikola Borislavov Kovachki, Kamyar Azizzadenesheli, Burigede liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar.  Fourier neural operator for parametric partial differential equations.  In _International Conference on Learning Representations_ , 2021.
  * Liu et al. (2021) Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 9992–10002, Los Alamitos, CA, USA, 10 2021. IEEE Computer Society.
  * Lorenz (1963) Edward N Lorenz.  Deterministic nonperiodic flow.  _Journal of atmospheric sciences_ , 20(2):130–141, 1963.
  * Martins et al. (2020) André Martins, António Farinhas, Marcos Treviso, Vlad Niculae, Pedro Aguiar, and Mario Figueiredo.  Sparse and continuous attention mechanisms.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 20989–21001. Curran Associates, Inc., 2020.
  * Moreno et al. (2022) Alexander Moreno, Zhenke Wu, Supriya Nagesh, Walter Dempsey, and James M Rehg.  Kernel multimodal continuous attention.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 18046–18059. Curran Associates, Inc., 2022.
  * Ovadia et al. (2023) Oded Ovadia, Adar Kahana, Panos Stinis, Eli Turkel, and George Em Karniadakis.  Vito: Vision transformer-operator.  _arXiv preprint_ , arXiv:2303.08891, 2023.
  * Pecora and Carroll (1990) Louis M. Pecora and Thomas L. Carroll.  Synchronization in chaotic systems.  _Phys. Rev. Lett._ , 64:821–824, 2 1990.
  * Pinkus (1999) Allan Pinkus.  Approximation theory of the mlp model in neural networks.  _Acta Numerica_ , 8:143–195, 1999.
  * Rahman et al. (2024) Md Ashiqur Rahman, Robert Joseph George, Mogab Elleithy, Daniel Leibovici, Zongyi Li, Boris Bonev, Colin White, Julius Berner, Raymond A. Yeh, Jean Kossaifi, Kamyar Azizzadenesheli, and Anima Anandkumar.  Pretraining codomain attention neural operators for solving multiphysics pdes.  _arXiv preprint_ , arXiv:2403.12553, 2024.
  * Ronneberger et al. (2015) Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In Nassir Navab, Joachim Hornegger, William M. Wells, and Alejandro F. Frangi, editors, _Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015_ , pages 234–241, Cham, 2015. Springer International Publishing.  ISBN 978-3-319-24574-4.
  * Sanz-Alonso et al. (2023) Daniel Sanz-Alonso, Andrew Stuart, and Armeen Taeb.  _Inverse Problems and Data Assimilation_.  London Mathematical Society Student Texts. Cambridge University Press, 2023.
  * Temam (2012) R. Temam.  _Infinite-Dimensional Dynamical Systems in Mechanics and Physics_.  Applied Mathematical Sciences. Springer New York, 2012.  ISBN 9781468403138.
  * Tsai et al. (2019) Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov.  Transformer dissection: An unified understanding for transformer’s attention via the lens of kernel.  In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan, editors, _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4344–4353, Hong Kong, China, November 2019. Association for Computational Linguistics.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Wen et al. (2023) Qingsong Wen, Tian Zhou, Chaoli Zhang, Weiqi Chen, Ziqing Ma, Junchi Yan, and Liang Sun.  Transformers in time series: A survey.  In _International Joint Conference on Artificial Intelligence(IJCAI)_ , 2023.
  * Wright and Gonzalez (2021) Matthew A Wright and Joseph E. Gonzalez.  Transformers are deep infinite-dimensional non-mercer binary kernel machines.  _arXiv preprint_ , arXiv:2106.01506, 2021.
  * Yun et al. (2020) Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar.  Are transformers universal approximators of sequence-to-sequence functions?  In _International Conference on Learning Representations_ , 2020.