# Self-Supervised Equivariant Scene Synthesis from Video

Cinjon Resnick
NYU
<EMAIL_ADDRESS>Or Litany
NVidia
Cosmas Heiß
Technical University of Berlin
Hugo Larochelle
Google
Joan Bruna
NYU
Kyunghyun Cho
NYU

###### Abstract

We propose a self-supervised framework to learn scene representations from
video that are automatically delineated into background, characters, and their
animations. Our method capitalizes on moving characters being equivariant with
respect to their transformation across frames and the background being
constant with respect to that same transformation. After training, we can
manipulate image encodings in real time to create unseen combinations of the
delineated components. As far as we know, we are the first method to perform
unsupervised extraction and synthesis of interpretable background, character,
and animation. We demonstrate results on three datasets: Moving MNIST with
backgrounds, 2D video game sprites, and Fashion Modeling.

##  1 Introduction

Learning manipulable representations of dynamic scenes is a challenging task.
Ideally, we would give our model a video and receive an inverse rendering of
coherent moving objects (‘characters’) along with a set of static backgrounds
through which those characters move.

A motivating example is creating a stop motion video in which each character
is painstakingly moved across static backgrounds to form the frames. Our goal
is to have a model train on any number of videos, each of which have an
independent set of characters and background, and then be able to synthesize
new scenes mixing and matching (possibly unseen) characters and the
backgrounds, thereby expediting the process of creating stop motion videos.
This long standing problem with no good solution (see Section 5) can be
thought of as unsupervised separation and synthesis of background and
foreground, and a strong solution would address other applications as well,
such as video compositing. Current unsupervised methods performing synthesis
are limited in that they either cannot handle backgrounds [16, 27, 10], cannot
synthesize the foreground and background independently [23, 22, 19], or cannot
handle animation [24].

Figure 1: Approach: We use neural networks to parameterize $f_{c}$, $f_{b}$,
$g$, and $T^{Z}$. With $f_{c}$, we encode the image to be transformed,
$x_{\mathrm{c}}$, as well as the two images, $x_{\mathrm{t1}}$ and
$x_{\mathrm{t2}}$, whose transformation we impose on $x_{\mathrm{c}}$. The
output of $T^{Z}$ is an affine matrix that we apply to
$f_{c}(x_{\mathrm{c}})$. That result is added to the background encoding
$f_{b}(x_{\mathrm{b}})$ and then decoded to yield
$\hat{x}=g(T^{Z}(f_{c}(x_{\mathrm{t1}}),f_{c}(x_{\mathrm{t2}}))\circ
f_{c}(x_{\mathrm{c}})+f_{b}(x_{\mathrm{b}}))$. For training, we require only
two distinct images, $(x_{i},x_{j})$, from the same video, where
$x_{i}=x_{\mathrm{c}}=x_{\mathrm{t1}}=x_{\mathrm{b}}$ and $\hat{x}$ should
approximate $x_{j}=x_{\mathrm{t2}}$. At test time, we can render new scenes
$\hat{x}$ where only $x_{\mathrm{t1}}$ and $x_{\mathrm{t2}}$ need to be from
the same sequence.

To be more specific, assume an input video of a dynamic scene captured by a
static camera. The background consists of the objects that are constant across
the frames. In contrast, the foreground consists of the objects that are
equivariant with respect to some family of transformations. We use this
difference to infer a scene representation that captures separately the
background and the characters. Building on Dupont et al. [5], we attain two
novel results:

  1. 1.

Learn the transformation We do not require the underlying transformation
applied to foreground objects during training, but instead learn it from
nearby video frames. At inference, this allows us to animate characters
according to any transformation and not just ones that include the character
being transformed.

  2. 2.

Distinguish characters and background: By independently encoding the
background and the manipulable character, we yield disentangled
representations for both and can mix and match them freely.

Our model is trained in a self-supervised fashion requiring only nearby frames
$(x^{i}_{p},x^{i}_{q})$ (without any annotation) from the $i$th video
sequence. We impose no other constraint and can render new scenes combining
characters and backgrounds on the fly with additional (potentially unrelated)
frames from sequences $x^{j}$ and $x^{k}$. In Sections 4.3 and 4.4
respectively, we show strong results on both Moving MNIST [21] with static
backgrounds and 2D video game sprites from the Liberated Pixel Cup [2] where
we demonstrate the following manipulations:

  * •

Render the character in $x^{i}_{m}$ but with the background from $x^{j}_{n}$.

  * •

Render the character in $x^{i}_{m}$ using the transformation seen in the
change from $x^{j}_{p}\rightarrow x^{j}_{q}$.

  * •

Combine both manipulations to render the character in $x^{i}_{m}$ on the
background from $x^{j}_{n}$ using the transformation exhibited by the change
seen from $x^{k}_{p}\rightarrow x^{k}_{q}$.

In Section 4.5, we report results on Fashion Modeling, a more realistic
dataset for which our results are not as mature.

##  2 Background

Following Dupont et al. [5], we define an image $x\in X=\mathbb{R}^{c\times
h\times w}$ and a scene representation $z\in Z=\mathbb{R}^{c^{\prime}\times
h^{\prime}\times w^{\prime}}$, a rendering function $g:Z\rightarrow X$ mapping
scene representations to images, and an inverse renderer $f:X\rightarrow Z$
mapping images to scene representations. It is helpful to consider $x$ as a 2D
rendering of a character $c$ from a specific camera viewpoint. An equivariant
scene representation $z$ satisfies the following relation for an equivariant
renderer $g$ with respect to transformation $T$:

$T^{X}g(z)=g(T^{Z}z)$ (1)

Figure 2: Labeling the rows as $x^{1},\ldots,x^{6}$, the first three are
ground truth, row $x^{4}$ pairs the background from $x^{2}$ and the character
from $x^{1}$, row $x^{5}$ pairs the character of $x^{1}$ with the animations
from $x^{3}$ and row $x^{6}$ combines both manipulations. With
counterclockwise direction and bottom left origin, the $x^{3}$ transformations
are rotate(15), rotate(9), translate(10, 4), translate(-8, -6).

In other words, transforming a rendering in image space is equivalent to first
transforming the scene in feature space and then rendering the result. Dupont
et al. posit functions $f$ and $g$ satisfying the following, where $x$ is a 2D
image rendering, $z$ is the scene representation of $x$, and $T^{Z}$ is an
affine transformation:

$x_{2}=T^{X}x_{1}=T^{X}g(z_{1})=g(T^{Z}z_{1})=g(T^{Z}f(x_{1}))$ (2)

Equation 2 is a difficult equality to satisfy, so they propose learning neural
networks $f,g$ to approximate it from data triples $(x_{1},x_{2},\theta)$,
where $x_{1},x_{2}$ are renderings of the same character $c$ and $\theta$ is a
rotation transforming $c$ from its appearance in $x_{1}$ to its appearance in
$x_{2}$. They assume $T^{Z}$ is the same operation as $T^{X}$ but in feature
space, and consequently apply a rotation of $\theta$ to the 3D representation
$z_{1}=f(x_{1})$. With $\tilde{z}_{1}=R^{Z}_{\theta}f(x_{1})$ and
$\tilde{z}_{2}=(R^{Z}_{\theta})^{-1}f(x_{2})$, they then train $g$ and $f$ to
minimize reconstruction loss:

$\displaystyle\mathbb{L}_{\text{render}}=||x_{2}-g(\tilde{z_{1}})||+||x_{1}-g(\tilde{z_{2}})||$
(3)

After training, new renderings can be inferred by first inverse rendering
$z=f(x)$, then applying rotations $T^{Z}$ upon $z$, and finally rendering
images $\hat{x}=g(T^{Z}z)$. In other words, the model operates entirely in
feature space. For their purposes, this lets them manipulate the output
rendering quickly and without access to the object in image space. As we show
in Section 3, this can be further extended to manipulations that are actually
very difficult to do in image space but become easy to do in feature space.

##  3 Method

Our motivation is in using the smoothly-changing nature of video to learn the
transformations between frames. Like Dupont et al., we assume that the change
between frames $F_{t}$ and $F_{t+1}$ can be modeled with affine
transformations. While they use only rotation, we assume an arbitrary affine
transformation on the character plus an invariant transformation on the
background, in-painting as needed. Accordingly, we remove the $\theta$
requirement at both training and test by learning the transformation $T^{Z}$
from data. A question arises – if we learn $T^{Z}$ from data, then why assume
that it is an affine operation? The first reason is that it biases $T^{Z}$
towards having a commonly used model for motion estimation. Second, it limits
us to six interpretable axes of variation in our animation, which lets us
compare directly against a ground truth affine transformation when given.
Finally, this approach also limits the operator’s ability to ‘hide’
information about the target image in the representation, exemplified by works
like CycleGAN [30] as demonstrated by Chu et al. [3].

#### Setup

Building on Section 2, we define $f_{b}$ and $f_{c}$ respectively representing
the encoding of the background and character. With scalar coefficients
$\alpha_{\text{equiv}}$, $\alpha_{\text{inv}}$, and denoting

$\displaystyle
h(x_{\mathrm{c}},x_{\mathrm{t1}},x_{\mathrm{t2}},x_{\mathrm{b}})$
$\displaystyle\quad=g(T^{Z}(f_{c}(x_{\mathrm{t1}}),f_{c}(x_{\mathrm{t2}}))\circ
f_{c}(x_{\mathrm{c}})+f_{b}(x_{\mathrm{b}}))$

we learn neural networks $f_{c}$, $f_{b}$, $g$, and $T^{Z}$ by minimizing
$\mathbb{L}_{\text{total}}$ below. During training, this requires a dataset
consisting of random pairs $(x_{1},x_{2})$ of frames from each clip where
$x_{1}$ and $x_{2}$ have roughly the same background.

$\displaystyle\mathbb{L}_{\text{total}}$
$\displaystyle=\mathbb{L}_{\text{scene}}+\alpha_{\text{equiv}}\mathbb{L}_{\text{equiv}}+\alpha_{\text{inv}}\mathbb{L}_{\text{inv}}$
(4)

where

$\displaystyle\mathbb{L}_{\text{scene}}$
$\displaystyle=||h(x_{1},x_{1},x_{2},x_{1})-x_{2}||_{2}$
$\displaystyle\mathbb{L}_{\text{equiv}}$
$\displaystyle=||T^{Z}(f_{c}(x_{1}),f_{c}(x_{2}))\circ
f_{c}(x_{1})-f_{c}(x_{2})||_{2}$ $\displaystyle\mathbb{L}_{\text{inv}}$
$\displaystyle=||f_{b}(x_{1})-f_{b}(x_{2})||_{2}$

Losses $\mathbb{L}_{\text{equiv}}$ and $\mathbb{L}_{\text{invariant}}$ help
with training, but they are not by themselves indicative of successful
training. We attain quality results only when $\mathbb{L}_{\text{scene}}$ is
sufficiently minimized. Other possible constraints, such as a transformation
inverse loss on
$T^{Z}(f_{c}(x_{\mathrm{t1}}),f_{c}(x_{\mathrm{t2}}))=T^{Z}(f_{c}(x_{\mathrm{t2}}),f_{c}(x_{\mathrm{t1}}))^{-1}$,
were not necessary.

Both $T^{Z}$ and $f_{c}$ learn to handle every character similarly. This is
important because it means that at inference time we can render novel scenes
given a pair of nearby frames in a video. The renderings described in Section
1 and demonstrated in Section 4 are now:

  * •

$h(x^{i}_{1},x^{i}_{1},x^{i}_{2},x^{j}_{1})$: Render the character in
$x^{i}_{1}$ as seen in $x^{i}_{2}$ but with the background from $x^{j}_{1}$.

  * •

$h(x^{j}_{1},x^{i}_{1},x^{i}_{2},x^{j}_{1})$: Render the character and
background in $x^{j}_{1}$ using the transformation exhibited by the change in
the character from $x^{i}_{1}\rightarrow x^{i}_{2}$.

  * •

$h(x^{i}_{1},x^{k}_{1},x^{k}_{2},x^{j}_{1})$: Combine the above two to render
the character in $x^{i}_{1}$ on the background from $x^{j}_{1}$ using the
transformation exhibited by the change in the character from
$x^{k}_{1}\rightarrow x^{k}_{2}$.

#### Learning the transformation.

The smoothly changing nature of video lets us advance past affine
transformations parametrically defined with a $\theta$ angle of rotation and
instead learn transformations based on frame changes. One advantage to this
approach is that the model becomes agnostic to which transformations the data
exhibits. We show this to be explicitly true for Moving MNIST and implicitly
true for Sprites, where the transformations are not affine. Another advantage
arises at inference time because the model is agnostic to whether the frame to
be transformed is input to the transformation function.

#### Distinguishing characters and background

The renderer $g$ is equivariant to character transformations. A static
background however will be constant across a video. We take advantage of this
to learn $g$ along with functions $f_{c}$ and $f_{b}$ corresponding to the
character and the background such that, at inference time, we can mix and
match characters and backgrounds previously never seen together.

##  4 Experiments

The first dataset is a variant of Moving MNIST [21] where we overlay each
sequence of moving digits on a randomly drawn background. Experiments on this
dataset lets us test our model on a wide range of explicit translations and
rotations in the digits.

The second dataset was debuted by Reed et al.[16] and consists of moving 2D
video game character sprites without any backgrounds, using graphic assets
from the Liberated Pixel Cup [2]. We perform experiments both with and without
backgrounds. These experiments test our model on more complex mappings like
firing a bow and arrow instead of just affine transformations in image space.

This test-bed is suitable for demonstrating that our method exhibits three
desirable capabilities: 1) Separate foreground from background; 2) Learn an
interpretable but complex transformation of the foreground in the feature
space; 3) Render transformed foreground objects. Furthermore, it allows us to
demonstrate generalization to unseen characters (digits and sprites) and
unseen backgrounds.

We also show results on a third dataset, Fashion Modeling, from Zablotskaia et
al. [29], consisting of videos of models exhibiting clothing without any
backgrounds. This dataset tests our model on realistic poses and fine detail.

###  4.1 Architecture

We parameterize $f_{c}$, $f_{b}$, $g$, and $T^{Z}$ with neural networks. While
separate, both $f_{c}$ and $f_{b}$ share the same architecture details as a
residual network. The renderer $g$ is a transposition of that architecture,
although we drop the residual components. Please see Figures 22, 23, 24 in the
Appendix for details.

The transformation $T^{Z}$ exhibits three properties. First, it is input-order
dependent. Second, it uses PyTorch’s [14] affine_grid and grid_sample
functions to transform the scene similarly to how Spatial Transformers [9]
operate. The third is that it is initialized as identity, reflecting our prior
that $T^{Z}$ does not alter the foreground.

###  4.2 Background Generation

We create $B$ randomly generated backgrounds for each of train, val, and test.
For each background, we select a color from the Matplotlib CSS4 colors list.
We then place five diamonds on the background, each with a different random
color, along with an independent and randomly chosen center and radius. The
radius is uniformly chosen from between seven and ten, inclusive.

For the Moving MNIST experiments, $B=64$ for each split because the model
overfit with $B<64$. For the Sprite experiments, we used $B=100$ for test but
a range of $B\in[64,128,256,784,1000]$ for training.

###  4.3 Moving MNIST

We generate videos, each of length $M=5$, of MNIST digits (characters) moving
on a static background. The digits and background have dimensions $(28,28)$
and $(64,64)$ respectively. At each training step, we select $N$ digits in the
train split of MNIST, as well as a background from the set of pre-generated
training backgrounds. We then randomly place these digits. For each digit, and
for each of $M-1$ times, we choose randomly between rotation and translation.
If translation, then we translate the character independently in each of the
$x$ and $y$ directions by a random amount in
$\\{-10,-8,\ldots,8,10\\}\setminus\\{0\\}$. If rotation, then we rotate the
character by a random amount in $\\{-15,-12,\ldots,12,15\\}\setminus\\{0\\}$.
If the character leaves the image boundaries, we redo the transformation
selection. Otherwise, that transformation is applied cumulatively to yield the
next character position.

This results in digits on blank canvases. We overlay them on the chosen
background to produce a sequence where the change in each character from
frames $F_{t}\rightarrow F_{t+1}$ is small and affine for the character and
constant for the background. This is performed by locating the (black) MNIST
pixels and blackening those locations on the canvases. Accordingly, we do not
use the black color canvas. We then randomly choose two indices $i,j$ and use
$(x_{i},x_{j})$ as the training pair. See Figure 2 for example sequences.

#### Qualitative Results

Our model learns to render new scenes using characters from the test set of
MNIST and held out backgrounds. All shown sequences are on unseen backgrounds
with unseen MNIST digits where there are at least two transformations of each
of rotation and translation.

Figure 2 convincingly demonstrates the manipulations from Section 3. The final
row is rendered by encoding the character from the first row, the background
from the second row, and using the transformations exhibited in the third row.
Denoting $x^{i}_{j}$ as the $j$th frame from the $i$th sequence:

$x^{6}_{k}=h(x_{\mathrm{c}}=x^{1}_{k},x_{\mathrm{t1}}=x^{3}_{1},x_{\mathrm{t2}}=x^{3}_{k},x_{\mathrm{b}}=x^{2}_{k})$

Figure 3: Per-pixel MSE over 10,000 test examples. The transform and
background manipulations use our learned functions; Video frames is MSE of a
frame against a random (non-identical) frame from the same video; No object is
MSE of the background versus the full frame of background and character.

#### Quantitative Results

We tested reconstruction by evaluating the per pixel MSE over the moving MNIST
test set. For each example, we randomly chose two pairs of (background, digit)
and made corresponding videos $(x^{1}_{1},\ldots,x^{1}_{5})$ and
$(x^{2}_{1},\ldots,x^{2}_{5})$. We then indexed into the same random position
in both sequences to get frame pairs $(x^{1}_{i},x^{1}_{j})$,
$(x^{2}_{i},x^{2}_{j})$. Fig 3 shows a boxplot comparing two manipulations,
Transformation and Background, along with two baselines, Video frames and No
object.

The predicted value for Transformation is
$\hat{x}^{2}_{j}=h(x^{2}_{i},x^{1}_{i},x^{1}_{j},x^{2}_{i})$. We compute an
MSE for this manipulation by comparing it against the ground truth attained by
rendering the background and character from $x^{2}_{i}$, transformed like seen
in $x^{1}_{i}\rightarrow x^{1}_{j}$. The predicted value for Background is
$\hat{x}^{1}_{j}=h(x^{1}_{i},x^{1}_{i},x^{1}_{j},x^{2}_{j})$. We compute an
MSE for this manipulation by comparing it against the rendering of the
character in $x^{1}_{j}$ on the background from $x^{2}_{j}$ with the original
transforms. Video frames is the MSE of two random frames from the same video.
No object is the MSE of a full frame against only the background from that
frame.

Given that MSE is a measure of reconstruction quality with lower values being
better, we expect them to serve as upper bounds. Video frames is the upper
bound when reconstruction gets the character but places it incorrectly. No
object is the upper bound when reconstruction fails to include the character.
On this measure, we see that the background manipulation is much better than
the baselines, but we cannot say with certitude that the transform
manipulation is better as it is within confidence interval of Video frames and
its boxplot overlaps with both baselines.

(a) Spellcast Animation

(b) Thrust Animation

(c) Shoot Animation

Figure 4: Transferring animations. In both panels, the first and second rows
are ground truth; Image $x^{3}_{i}$ in the third row is given by applying the
transformation exhibited by $x^{1}_{1}\rightarrow x^{1}_{i}$ to $x^{2}_{0}$.
Observe how in panel (b) that a spear is not hallucinated, but instead the
thrust action is applied to the character without a spear. And in panel (c),
even though there is no bow in the input to the transformation, the model
understands to move the bow and pull the string in the character upon which
the transformation is applied. Figure 5: The rows are background manipulation
$x^{1}_{4}=h(x^{1}_{1},x^{1}_{1},x^{1}_{2},x^{1}_{3})$, animation transfer
$x^{2}_{4}=h(x^{2}_{3},x^{2}_{1},x^{2}_{2},x^{2}_{3})$, and both combined
$x^{3}_{5}=h(x^{3}_{3},x^{3}_{1},x^{3}_{2},x^{3}_{4})$.

###  4.4 Video Game Sprites

The dataset comprises $60\times 60$ color images of sprites with seven
attributes (sex, body type, arm, hair, armor, greaves, and weapon) for a total
of 672 unique characters. We use the same dataset splits as Reed et al. with
500 training characters, 72 validation characters, and 100 test characters.
For each character, there are four viewpoints for each of five animations:
spellcast, thrust, walk, slash, and shoot. Our sequences are the twenty
animations per character, which have between six and thirteen frames. We only
show results on test characters and a held out set of test backgrounds.

For results without backgrounds, we select a random sequence and then two
random frames $(x_{i},x_{j})$ from that sequence as input to our model. For
results with backgrounds, we additionally choose a random background and then
use the provided masks to center the sprite data on top of the background. See
Figures 4, 5 for examples of sequences without and with backgrounds.

#### Qualitative Results

Figure 4 shows strong results on three different types of animations
(spellcast, thrust, shoot) without backgrounds. In each panel, the first and
second rows are ground truth, as is the first frame of the third row –
$x^{3}_{1}$ ($=x^{2}_{1}$). The rest of the third row is animating $x^{3}_{1}$
according to the transformations exhibited by the first row. In all three
panels, the major concern is with the hand color. The model occasionally
blends the green hands of the original character with that of the character
being animated. In the first panel, this appears as gray, while in the second
and third panels it has a green tint. On the other hand, the model
successfully performs the thrusting action without hallucinating a spear in
the second panel. Similarly, the model operates the bow and arrow in the third
panel, even though there is only the shooting motion and not the actual bow in
the first row.

Figure 5 shows results when using backgrounds. We see an example of each of
the type of manipulations from Section 3. The first row is changing the
background, the second row is animation transfer, and the third row is
performing both background change and animation transfer. The model is strong
but clearly not perfect at this task. In addition to the hand discoloring (2nd
row), we also see that the backgrounds are a bit blurry near the character in
all three rows.

#### Quantitative Results

For results without backgrounds, we tested reconstruction by evaluating the
per pixel MSE over the test set. Figure 6 compares our approach against prior
work on analogy reconstruction. We are competitive in every category and the
most consistent in our results, with Figure 7 showing that our model is
capable across all categories. This is in contrast to the model with the best
average performance from Xue et al. [28], ‘VD’, which performs poorly on the
slash category. We further show our model’s flexibility by taking a version
trained with diamond backgrounds and ask it to perform the same analogy task
but with a fixed gray canvas as the input to the background encoder. We use
gray because the model never saw black in its training process. Figure 6 shows
that this model, ‘Ours-BG’, attains comparable results. Examples from ‘Ours-
BG’ and a representative MSE boxplot are in the Appendix (Figures 16, 17).

Figure 6: Reconstructing analogous sprites without backgrounds in pixel MSE,
with max cutoff at 60.0. Our method is competitive in every category and has
much lower variance than the other models, even though it was designed for
datasets with affine transformations and backgrounds, both of which are
missing in this context. We highlight our model’s flexibility by using a model
trained with diamond backgrounds (‘Ours-BG’), asking it to remove the
background, and still yielding comparable results. Figure 7: A boxplot of
sprite analogy reconstruction MSE without backgrounds. This expands upon the
reported averages in Figure 6.

For sprite results with backgrounds, we similarly evaluate per-pixel MSE
evaluation in Figure 9. We include only the aggregate boxplots and put the
full breakdown in the Appendix (Figure 21). The first boxplot, ‘Analogy’,
represents analogy reconstruction. It shows a clear (expected) increase in MSE
over reconstruction without backgrounds. Is this due to the background or the
character?

To answer that question, we utilize the provided character mask. Boxplot
‘Background-only’ is the resulting MSE from masking out where the character
should be in both the predicted and ground truth and then computing MSE over
just the unmasked part, presumed to be the background. Boxplot ‘Character-
only’ is similar but masking out everything but where the character should be
and computing MSE over the presumed character. ‘Background-only’ MSE remains
consistent but is also much lower than ‘Analogy’, with an aggregate of $28.5$.
In contrast, the ‘Character-only‘ aggregate MSE is $79.0$ with a high of
$83.3$ (slash) and a low of $73.3$ (spell). This analysis suggests that the
loss in MSE is dominantly due to the character reconstruction. This is
encouraging for improving our results given the litany of recent techniques
[19, 20, 29, 22] focusing on character animation in similar settings that can
be coupled with our method.

Figure 8: Analogy reconstruction with backgrounds. The more the number of
backgrounds used during training, the better the model does at test set
reconstruction. This effect tapers near 1000. Figure 9: Sprite analogy
reconstruction with backgrounds over all animation types. Compared to Figure
7, the ‘Analogy’ boxplot shows an (expected) increase in MSE. The other two
boxplots highlight that this is dominantly due to character reconstruction
rather than background reconstruction.

Figure 10: In both panels, the first four columns are ground truth. The fifth
is the model’s output when inputting just the background encoding to the
decoder $g$. The sixth is the output when inputting just the transformed
character encoding to $g$. The last column is including both as input to $g$.
Notice how the model separates the character and the background more cleanly
in Moving MNIST. This is because the characters move throughout the scene and
so the model has distinguishing information about all areas of the frame.
Figure 15 in the Appendix shows that when the sprite moves during training in
only a single cardinal direction, the model learns a similarly clean
separation.

###  4.5 Fashion Modeling

| Perceptual ($\downarrow$) | FID ($\downarrow$) | AKD ($\downarrow$)
---|---|---|---
MonkeyNet [18] | 0.3726 | 19.74 | 2.47
CBTI [8] | 0.6434 | 66.50 | 4.20
DwNet [29] | 0.2811 | 13.09 | 1.36
Ours | 0.4222 | 70.87 | 13.06
Table 1: Comparison with state-of-the-art on Fashion.

Table 1 compares our results on Fashion Modeling against the current state of
the art. While our model is capable of learning the transformation, it is not
up to par with respect to realism. We consider this to be a question of model
architecture and training and are actively working to improve this result. One
direction is to adopt the 3D architecture from Dupont et al, which we expect
to improve our results greatly given the common output errors. See Figures 25,
26 in the Appendix for example renderings.

###  4.6 Analyzing $T^{Z}$

There must be structure in $T^{Z}$ because of its success animating
characters. We analyze this with Moving MNIST because we can compare $T^{Z}$
to the ground truth character transformation in $T^{X}$. For Sprites, that
comparison is more difficult because the ground truth is categorical. We
gather $40,000$ unique frame pairs of a fixed digit instance on a fixed
background, and show results for 8 and 5.

We make an assumption that there is structure in the MNIST $T^{Z}$ with
respect to both translation and rotation parameters independently. Figure 12
shows a kernel density estimation plot for the euclidean norm of the
translation parameters for digit $5$ (see Figure 14 in the Appendix for digit
$8$), attained by isolating the third column of the affine matrices. While
these are the only parameters corresponding to translation in the gathered
$T^{X}$, we caution that there may be more parameters effecting translation in
$T^{Z}$ due to how affine matrices combine. Observe though how strongly
coupled and linear is the relationship between these norms, with almost all of
the joint density lying in a small range centered at about $(15,0.6)$.

For rotations on MNIST, it is trivial to parse the angle from $T^{X}$ as the
arctan of the first column in the corresponding affine linear matrix. This is
not true of $T^{Z}$ because it is an unconstrained prediction with entries
violating the conditions of a rotation matrix. This observation is supported
by Figure 11, which shows the density plot for the top left entry of the
$2\times 3$ matrix of transformations. It is apparent that $T^{Z}$, contrary
to $T^{X}$, cannot correspond to only translation and rotation in how it
manipulates the feature space because these entries have too high of a
magnitude. Consequently, we use SVD [7] to decompose $T^{Z}=USV^{T}$, and
yield the best approximating rotation matrix $R=UV^{T}$ [1]. We then use the
angle from $R$ as the prediction and compare it the angle attained from
$T^{X}$. Their exceptionally linear relationship can be observed for both
digits in Figure 13.

The relationship seen in these figures is further supported by a linear
regression from $T^{X}$ to $T^{Z}$. We flatten both to $6$ dimensional
representations and use sklearn’s LinearRegression package [15]. As expected,
the $r^{2}$ score for each digit is exceptionally high, $0.992$ for digit 5
and $0.993$ for digit 8.

Altogether, this analysis suggests that the learned $T^{Z}$ has a strong
linear relationship with the ground truth $T^{X}$, even though $T^{Z}$ had no
prior knowledge of $T^{X}$. Furthermore, it also suggests that even though
$T^{Z}$ and $T^{X}$ have very different statistics (exemplified by the two
plots in Figure 11), $T^{Z}\circ f_{c}(x_{c})$ is not actually that different
from $T^{X}$ in how it manipulates the image space, which is what we desire.

Figure 11: Transformation densities over 40,000 (MNIST) and 105,000 (Sprites)
random, unique frame pairs. The left plot is of the largest singular value of
the affine transformation, where $T^{X}$ is not shown as its upper left square
matrix is always unitary. The right plot is of the top left entry in the
matrix; positive density for $T^{X}$ value $>1$ is a plotting artifact. Figure
12: Kernel density estimation plot of the euclidean norm of the translation
parameters for Moving MNIST, with $T^{Z}$ on the y-axis and $T^{X}$ on the
x-axis. Figure 13: Moving MNIST scatterplot comparing the rotation angle of
$T^{Z}$ against the rotation angle of $T^{X}$. The latter is ground truth,
while the former is attained from the rotation matrix $R=UV^{T}$ we yield from
decomposing $T^{Z}$ into $U,S,V^{T}$ matrices with SVD.

##  5 Related Work

Both the problem of background and foreground separation, as well as that of
manipulable synthesis, are longstanding concerns in unsupervised learning [11,
6, 25, 17, 23, 4]. As far as we know, we are the first to perform both without
strong supervision such that we can independently manipulate each of the
animation, the background, and the character.

Besides Dupont et al. [5], the most closely related papers are Worrall et al.
[26], Olszewski et al. [13], and Reed et al. [16]. The first two also use
equivariance to learn representations capable of manipulating scenes. However,
they do not delineate characters and backgrounds, nor do they learn the
$T^{Z}$ from data. Dupont et al. assumes that $T^{Z}$ is given during
training; In Worrall et al., $T^{Z}$ is a block diagonal composition of
(given) domain-specific transformations; Olszewski et al. uses a user-provided
transformation. Because we learn $T^{Z}$ from data, we can use datasets
without ground truth like Sprites [2]. Reed et al. similarly applies
transformations to frames to yield an analogous frame. Where we use affine
transform, they use addition. They also require three frames as input to
$T^{Z}$ at inference and four frames during training. Most problematic is that
they require the full analogy during training. This means they cannot learn
the transformation from random pair frames like we do but instead require a
carefully built training set.

The papers from Siarohin et al. [19, 20] also use just pairs of images at
training time and can then animate an unseen character at inference. They do
not handle backgrounds independently and consequently are not able to mix and
match foreground and background without artifacts. MonkeyNet [18] and
Zablotskaia et al. [29] are also in this lineage and use the inductive bias
provided by DensePose (and a warping module for the latter). They similarly
focus on just modeling the character and place the background as is.

There are approaches that decompose the latent spaces with GANs [12, 22] or
VAEs [27, 10]. Most have the same concern synthesizing the background and
foreground independently with no mechanism for delineating the two, even
though there may be mechanisms for parsing the foreground like in Kosiorek et
al. [10]. Vondrick et al. [24] does have such a mechanism, however it serves
only to separate background from character pixels through a masking function.
Because our mechanism acts on the learned character function, we are able to
model the animation as well.

##  6 Conclusion

We have presented a self-supervised framework for learning an equivariant
renderer capable of delineating the background, the characters, and their
animation such that it can manipulate and synthesize each independently. Our
framework requires only video sequences. We tested it on two datasets chosen
to highlight the model’s capability in handling both truly affine movements
(Moving MNIST) as well as movements from video (Sprites). We then showed that
it can produce convincing and consistent scene manipulations, both of
background and animation transfer. Our analysis revealed a strong association
between the learned $T^{Z}$ and the ground-truth $T^{X}$, which was never seen
during training, implying the effectiveness of the proposed self-supervised
learning criterion. We also observed aspects of $T^{Z}$ not fully explained by
$T^{X}$.

An assumption that $T^{X}$ is affine does not hold in general; a clear
counterexample is videos with nonlinear lighting effects. However, there is no
reason why such an assumption on $T^{Z}$ could not hold. Consequently, we do
not see any barriers to our approach working on real-world examples such as
the motivating stop-motion animation. While our results are not yet strong
enough on complex real-world applications (see Section 4.5), we see this work
as being a promising step in that direction and leave that advance for future
work.

## References

  * [1] K.S. Arun, T.S. Huang, and Steven Blostein.  Least-squares fitting of two 3-d point sets. ieee t pattern anal.  Pattern Analysis and Machine Intelligence, IEEE Transactions on, PAMI-9:698 – 700, 10 1987.
  * [2] Bart.  About the liberated pixel cup, Jul 2012.
  * [3] Casey Chu, Andrey Zhmoginov, and Mark Sandler.  Cyclegan, a master of steganography.  CoRR, abs/1712.02950, 2017.
  * [4] Emily L Denton and vighnesh Birodkar.  Unsupervised learning of disentangled representations from video.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30, pages 4414–4423. Curran Associates, Inc., 2017\.
  * [5] Emilien Dupont, Miguel Angel Bautista, Alex Colburn, Aditya Sankar, Carlos Guestrin, Josh Susskind, and Qi Shan.  Equivariant neural rendering, 2020.
  * [6] B. J. Frey and N. Jojic.  Estimating mixture models of images and inferring spatial transformations using the em algorithm.  In Proceedings. 1999 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No PR00149), volume 1, pages 416–422 Vol. 1, 1999.
  * [7] G. H. Golub and C. Reinsch.  Singular value decomposition and least squares solutions.  Numer. Math., 14(5):403–420, Apr. 1970.
  * [8] Artur Grigorev, Artem Sevastopolsky, Alexander Vakhitov, and Victor S. Lempitsky.  Coordinate-based texture inpainting for pose-guided image generation.  CoRR, abs/1811.11459, 2018.
  * [9] Max Jaderberg, Karen Simonyan, Andrew Zisserman, and Koray Kavukcuoglu.  Spatial transformer networks.  CoRR, abs/1506.02025, 2015.
  * [10] Adam Roman Kosiorek, Hyunjik Kim, Ingmar Posner, and Yee Whye Teh.  Sequential attend, infer, repeat: Generative modelling of moving objects.  In Advances in Neural Information Processing Systems, 2018.
  * [11] Nicolas Le Roux, Nicolas Heess, Jamie Shotton, and John Winn.  Learning a generative model of images by factoring appearance and shape.  Neural Computation, 23:593–650, March 2011.
  * [12] Michaël Mathieu, Junbo Jake Zhao, Pablo Sprechmann, Aditya Ramesh, and Yann LeCun.  Disentangling factors of variation in deep representations using adversarial training.  CoRR, abs/1611.03383, 2016.
  * [13] Kyle Olszewski, Sergey Tulyakov, Oliver J. Woodford, Hao Li, and Linjie Luo.  Transformable bottleneck networks.  CoRR, abs/1904.06458, 2019.
  * [14] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic differentiation in pytorch.  2017\.
  * [15] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [16] Scott E Reed, Yi Zhang, Yuting Zhang, and Honglak Lee.  Deep visual analogy-making.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 1252–1260. Curran Associates, Inc., 2015.
  * [17] Michael Rubinstein, Armand Joulin, Johannes Kopf, and Ce Liu.  Unsupervised joint object discovery and segmentation in internet images.  IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), June 2013.
  * [18] Aliaksandr Siarohin, Stéphane Lathuilière, Sergey Tulyakov, Elisa Ricci, and Nicu Sebe.  Animating arbitrary objects via deep motion transfer.  CoRR, abs/1812.08861, 2018.
  * [19] Aliaksandr Siarohin, Stéphane Lathuilière, Sergey Tulyakov, Elisa Ricci, and Nicu Sebe.  First order motion model for image animation, 2020.
  * [20] Aliaksandr Siarohin, Subhankar Roy, Stéphane Lathuilière, Sergey Tulyakov, Elisa Ricci, and Nicu Sebe.  Motion-supervised co-part segmentation, 2020.
  * [21] Nitish Srivastava, Elman Mansimov, and Ruslan Salakhutdinov.  Unsupervised learning of video representations using lstms.  CoRR, abs/1502.04681, 2015.
  * [22] Sergey Tulyakov, Ming-Yu Liu, Xiaodong Yang, and Jan Kautz.  Mocogan: Decomposing motion and content for video generation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [23] Ruben Villegas, Jimei Yang, Seunghoon Hong, Xunyu Lin, and Honglak Lee.  Decomposing motion and content for natural video sequence prediction.  CoRR, abs/1706.08033, 2017.
  * [24] Carl Vondrick, Hamed Pirsiavash, and Antonio Torralba.  Generating videos with scene dynamics.  CoRR, abs/1609.02612, 2016.
  * [25] Christopher Williams and Michalis Titsias.  Greedy learning of multiple objects in images using robust statistics and factorial learning.  Neural computation, 16:1039–62, 06 2004.
  * [26] Daniel E. Worrall, Stephan J. Garbin, Daniyar Turmukhambetov, and Gabriel J. Brostow.  Interpretable transformations with encoder-decoder networks.  CoRR, abs/1710.07307, 2017.
  * [27] Tianfan Xue, Jiajun Wu, Katherine L Bouman, and William T Freeman.  Visual dynamics: Probabilistic future frame synthesis via cross convolutional networks.  In Advances In Neural Information Processing Systems, 2016.
  * [28] Tianfan Xue, Jiajun Wu, Katherine L. Bouman, and William T. Freeman.  Visual dynamics: Probabilistic future frame synthesis via cross convolutional networks.  CoRR, abs/1607.02586, 2016.
  * [29] Polina Zablotskaia, Aliaksandr Siarohin, Bo Zhao, and Leonid Sigal.  Dwnet: Dense warp-based network for pose-guided human video generation.  CoRR, abs/1910.09139, 2019.
  * [30] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In Computer Vision (ICCV), 2017 IEEE International Conference on, 2017.

## Appendix

Figure 14: Matching KDE plot for digit 8. See Figure 12 in the main text for
digit 5. Figure 15: Panel referenced by Figure 10 showing five results from a
model trained with sprites undergoing x-translation during training in
addition to the normal changes in the character animation. Observe that the
model learns a clean separation of background and character in this case.
Figure 16: MSE plot for reconstructing analogies on blank canvases using a
model trained with backgrounds. See Figures 3, 6 for matching analysis and
Figure 17 for examples. Note that we did not use black backgrounds for the
reconstruction but gray ones instead. This is because the model was never
trained with the color black and it would be out of scope to generalize to a
completely new color.

Figure 17: Example sequences of removing the background. The first two columns
are the animation, the third column is the character, and the fourth column is
the character on a bare background. These inputs yield the output seen in the
sixth column which can be compared to the ground truth expected output in the
fifth column. Figure 18: Reconstructions: The first, third, and fifth rows are
original sequences. The second, fourth, and sixth rows are reconstructions of
the prior row where $T^{Z}$ is fixed as the same transformation as $T^{X}$.
Note that in these scenarios, the results are not as strong as when $T^{Z}$ is
a learned function. Figure 19: Backgrounds: The first, second, and fourth rows
are originals. The third and fifth rows are the prior row but with the
background changed to that of the first sequence. Figure 20: Transformations:
The first, second, and fourth rows are originals. The third and fifth rows are
the prior row but the transformation is a function of the first row.

(a) Analogy MSE

(b) Background-only MSE

(c) Character-only MSE

Figure 21: Analogy reconstruction with backgrounds. As expected, the model’s
MSE increases when incorporating backgrounds. Panels (b) and (c) show that
this is dominantly due to reconstructing the character and not the background.
Figure 22: Architecture of the Encoder for both characters and backgrounds.
Figure 23: Architecture of the Decoder. Figure 24: Architecture of $T^{Z}$.
Figure 25: Fashion reconstructions. The first column serves as $x_{c}$,
$x_{t1}$, and $x_{b}$, the second as $x_{t2}$ and the target. In the first
row, we can see that the model is not sure what to do with the legs. In the
second and third rows, the model has successfully repositioned the character
but remains blurry.

Figure 26: Fashion analogies. The first and second columns represent the
animation to be done to the character in the third column. The first and
fourth rows show successful animations, even with the slight animation in the
latter. The second row is facing the wrong direction. The third row should
have her arm still up and her leg moved to the side.


S]-\Pr_{x\sim\mathcal{D}_{2}}[x\in S]\Big{|}\Big{)}.$

######  Definition A.3.

Given a $q$-query deterministic algorithm $\mathcal{A}$, let $a(x)$ be the
string of $q$ answers that $\mathcal{A}$ receives when making queries to input
object $x$. For a distribution $\mathcal{D}$ and adversarial strategy
$\mathcal{S}$, let $\mathcal{D}$-view be the distribution on strings $a(x)$
where the input object $x$ is sampled from $\mathcal{D}$ and accessed via a
$t$-online-erasure oracle using strategy $\mathcal{S}$.

######  Corollary A.4.

To prove a lower bound $q$ on the worst-case query complexity of online-
erasure-resilient randomized algorithms for a promise decision problem, it is
enough to give

  * •

a randomized adversarial strategy $\mathcal{S}$,

  * •

a distribution $\mathcal{D}^{+}$ on positive instances of size $n$, and

  * •

a distribution $\mathcal{D}^{-}$ on instances of size $n$ that are negative
with probability at least $\frac{6}{7}$,

such that $CD(\mathcal{D}^{+}$-view$,\mathcal{D}^{-}$-view$)<\frac{1}{6}$ for
every deterministic $q$-query algorithm that accesses its input via an online-
erasure oracle using strategy $\mathcal{S}$.

We prove A.4, following an argument in [57]. We rely on the following claim
from [57].

######  Claim A.5 (Claim 4 of [57]).

Let $E$ be an event that happens with probability at least $1-\delta$ under
the distribution $\mathcal{D}$ and let $\mathcal{B}$ be the distribution
$\mathcal{D}$ conditioned on $E$. Then
$CD(\mathcal{D},\mathcal{B})\leq\delta^{\prime}$, where
$\delta^{\prime}=\frac{1}{1-\delta}-1$.

###### Proof of A.4.

Let $A$ be a deterministic $q$-query algorithm for the promise decision
problem. Given distributions $\mathcal{D}^{+}$ and $\mathcal{D}^{-}$, we
define a distribution $\mathcal{D}$ satisfying the conditions of Theorem A.1.
Let $E$ be the event that $x\sim\mathcal{D}^{-}$ is a negative instance, and
let $\mathcal{B}$ be the distribution $\mathcal{D}^{-}$ conditioned on the
event $E$. To obtain a sample from $\mathcal{D}$, with probability $1/2$ draw
a sample from $\mathcal{D}^{+}$, and with probability $1/2$ draw a sample from
$\mathcal{B}$. We show that $A$ errs with probability at least $1/3$ when it
accesses an input object $x\sim\mathcal{D}$ via the online-erasure oracle that
uses strategy $\mathcal{S}$. Let $Q$ be the set of query-answers strings $a$
on which $A$ accepts. By the law of total probability,

$\displaystyle\Pr_{x\sim\mathcal{D}}[A(x)\textnormal{ is correct}]$
$\displaystyle=\frac{1}{2}\Pr_{x\sim\mathcal{D}^{+}}[A(x)\textnormal{
accepts}]+\frac{1}{2}\Pr_{x\sim\mathcal{B}}[A(x)\textnormal{ rejects}]$
$\displaystyle=\frac{1}{2}+\frac{1}{2}\Big{(}\Pr_{x\sim\mathcal{D}^{+}}[A(x)\textnormal{
accepts}]-\Pr_{x\sim\mathcal{B}}[A(x)\textnormal{ accepts}]\Big{)}$
$\displaystyle=\frac{1}{2}+\frac{1}{2}\Big{(}\Pr_{a\sim\mathcal{D}^{+}\text{-view}}[a\in
Q]-\Pr_{a\sim\mathcal{B}\text{-view}}[a\in Q]\Big{)}$
$\displaystyle\leq\frac{1}{2}+\frac{1}{2}CD(\mathcal{D}^{+}\text{-view},\mathcal{B}\text{-view}).$

Note that $\mathcal{B}\text{-view}$ is the same as the distribution
$\mathcal{D}^{-}\text{-view}$ conditioned on the event $E$. By A.5 and the
assumption that $\Pr_{x\sim\mathcal{D}^{-}}[E]\geq\frac{6}{7}$, we have
$CD(\mathcal{B}\text{-view},\mathcal{D}^{-}\text{-view})\leq\frac{1}{6}$. By
the triangle inequality,

$CD(\mathcal{D}^{+}\text{-view},\mathcal{B}\text{-view})\leq
CD(\mathcal{D}^{+}\text{-view},\mathcal{D}^{-}\text{-view})+CD(\mathcal{B}\text{-view},\mathcal{D}^{-}\text{-view},)<\frac{1}{6}+\frac{1}{6}=\frac{1}{3}.$

Therefore, $\Pr_{x\sim\mathcal{D}}[A(x)\textnormal{ is
correct}]<\frac{1}{2}+\frac{1}{2}\cdot\frac{1}{3}=\frac{2}{3}$. ∎

##  Appendix B An Online-Erasure-Resilient Linearity Tester with
$O(t/\varepsilon)$ Queries

In this section, we present our online-erasure-resilient linearity tester with
query complexity $O(t/\varepsilon)$ (Algorithm 3) and prove Theorem B.1 below
that, together with Theorem 2.1, implies Theorem 1.1.

######  Theorem B.1.

There exist a constant $c_{0}\in(0,1)$ and a 1-sided error, nonadaptive,
$t$-online-erasure-resilient $\varepsilon$-tester for linearity of functions
$f\colon\\{0,1\\}^{d}\to\\{0,1\\}$ that works for $t\leq
c_{0}\cdot\varepsilon\cdot 2^{d/4}$ and makes $O(\frac{t}{\varepsilon})$
queries.

Algorithm 3 An Online-Erasure-Resilient Linearity Tester

1:$\varepsilon\in(0,\frac{1}{2})$, erasure budget $t\in\mathbb{N}$, access to
function $f:\\{0,1\\}^{d}\rightarrow\\{0,1\\}$ via a $t$-online-erasure
oracle.

2:Let $c=88$ and $q=\>\frac{ct}{\varepsilon}$.

3:for all $i\in[q]$:

4:Sample $x_{i}\sim\\{0,1\\}^{d}$ and query $f$ at $x_{i}$.

5:repeat $\frac{24}{\varepsilon}$ times:

6:Sample a uniform $(i,j)$ such that $i,j\in[q]$ and $i<j$, then query $f$ at
$x_{i}\oplus x_{j}$.

7:Reject if $x_{i},x_{j}$, and $x_{i}\oplus x_{j}$ are nonerased and
$f(x_{i})+f(x_{j})\neq f(x_{i}\oplus x_{j})$.

8:Accept.

In the analysis of Algorithm 3, we let $x_{i}$, for all $i\in[q]$, be random
variables denoting the points queried in Step 4. Recall that a pair $(x,y)$ of
domain points _violates_ linearity if $f(x)+f(y)\neq f(x\oplus y)$. The proof
of Theorem B.1 crucially relies on the following lemma about the concentration
of pairs violating linearity.

######  Lemma B.2.

Suppose $f$ is $\varepsilon$-far from linear and $q=\frac{ct}{\varepsilon}$.
Let $Y$ denote the number of pairs $(i,j)\in[q]^{2}$ such that $i<j$ and
$(x_{i},x_{j})$ violates linearity. Then
$\Pr[Y\leq\frac{\varepsilon}{4}\cdot{q\choose 2}]\leq 0.25$.

We prove B.2 in subsection B.1. In the rest of this section, we first prove an
auxiliary lemma (B.3) and then use Lemmas B.2 and B.3 to prove Theorem B.1.

We say a query $u\in\\{0,1\\}^{d}$ is successfully obtained if it is nonerased
right before it is queried, i.e., the tester obtains $f(u)$ as opposed to the
symbol $\perp$.

######  Lemma B.3.

Let $G_{1}$ be the (good) event that all ${q\choose 2}$ sums $x_{i}\oplus
x_{j}$ of points queried in Step 4 of Algorithm 3 are distinct, and $G_{2}$ be
the (good) event that all $q$ points $x_{i}$ queried in Step 4 are
successfully obtained. Then $\Pr[\overline{G_{1}}\cup\overline{G_{2}}]\leq
0.05$ for all adversarial strategies.

###### Proof.

First, we analyze event $G_{1}$. Consider points
$x_{i},x_{j},x_{k},x_{\ell}\sim\\{0,1\\}^{d}$, where
$\\{i,j\\}\neq\\{k,\ell\\}$. Since these points are distributed uniformly and
independently, so are the sums $x_{i}\oplus x_{j}$ and $x_{k}\oplus x_{\ell}$.
The probability that two uniformly and independently sampled points
$x,y\sim\\{0,1\\}^{d}$ are identical is $\frac{1}{2^{d}}$. Therefore, by a
union bound over all pairs of sums,
$\Pr[\overline{G_{1}}]\leq\binom{q}{2}^{2}\cdot\frac{1}{2^{d}}\leq\frac{q^{4}}{4\cdot
2^{d}}.$

To analyze $G_{2},$ fix an arbitrary adversarial strategy. In Steps 3-4, the
algorithm makes at most $q$ queries. Hence the oracle erases at most $qt$
points from $\\{0,1\\}^{d}$. Since each point $x_{i}$ is sampled uniformly
from $\\{0,1\\}^{d}$,

$\Pr_{x_{i}\sim\\{0,1\\}^{d}}[x_{i}\textnormal{ is erased when
queried}]\leq\frac{qt}{2^{d}}.$

By a union bound over the $q$ points sampled in Step 4, we get
$\Pr[\overline{G_{2}}]\leq\frac{q^{2}t}{2^{d}}$. We substitute
$q=\frac{ct}{\varepsilon}$ to get

$\displaystyle\Pr[\overline{G_{1}}\cup\overline{G_{2}}]\leq\frac{q^{4}}{4\cdot
2^{d}}+\frac{q^{2}t}{2^{d}}\leq\frac{q^{4}}{2^{d}}=\frac{c^{4}t^{4}}{\varepsilon^{4}\cdot
2^{d}}\leq c^{4}c_{0}^{4}\leq 0.05,$

since $t\leq c_{0}\cdot\varepsilon\cdot 2^{d/4}$, as stated in Theorem B.1,
and assuming $c_{0}$ is sufficiently small. ∎

###### Proof of Theorem B.1.

The query complexity of Algorithm 3 is evident from its description. Clearly,
Algorithm 3 is nonadaptive and accepts if $f$ is linear. Suppose now that $f$
is $\varepsilon$-far from linear and fix an arbitrary adversarial strategy. We
show that Algorithm 3 rejects with probability at least $\frac{2}{3}$.

We call a sum $x_{i}\oplus x_{j}$ queried in Step 6 violating if the pair
$(x_{i},x_{j})$ violates linearity. For Algorithm 3 to reject, it must sample
$i,j\in[q]$ such that $x_{i},x_{j},$ and $x_{i}\oplus x_{j}$ are successfully
obtained and $x_{i}\oplus x_{j}$ is a violating sum. Let $E_{k},$ for all
$k\in[24/\varepsilon],$ be the event that in iteration $k$ of Step 5, the
algorithm successfully obtains a violating sum. Let
$E=\bigcup_{k\in[24/\varepsilon]}E_{k}$. We define the following good event
concerning the execution of the for loop: $G=G_{1}\cap G_{2}\cap G_{3},$ where
$G_{1}$ and $G_{2}$ are as defined in B.3, and $G_{3}$ is the event that $Y$,
defined in B.2, is at least $\frac{\varepsilon}{4}\cdot{q\choose 2}$. By a
union bound and Lemmas B.2 and B.3, we know that $\Pr[G]\geq 0.7.$ Therefore,
the probability that Algorithm 3 rejects is at least

$\displaystyle\Pr[E\cap G]=\Pr[G]\cdot\Pr[E|G]\geq 0.7\cdot\Pr[E|G].$

Suppose that $G$ occurs for the execution of the for loop. Since $G_{2}$
occurred, all $q$ points queried in Step 4 of Algorithm 3 were successfully
obtained. So, the algorithm will reject as soon as it successfully obtains a
violating sum. Since $G_{1}$ occurred, there are at least $\binom{q}{2}$
distinct sums that can be queried in Step 6. Since $G_{3}$ occurred, at least
$\frac{\varepsilon}{4}\cdot\binom{q}{2}$ of them are violating. The total
number of erasures the adversary makes over the course of the entire execution
is at most $2qt$, since Algorithm 3 queries at most $2q$ points. Therefore,
the fraction of sums that are nonerased and violating before each iteration of
Step 6 is at least

$\displaystyle\frac{\varepsilon}{4}-\frac{2qt}{\binom{q}{2}}\geq\frac{\varepsilon}{4}-\frac{5t}{q}=\frac{\varepsilon}{4}-\frac{5\varepsilon}{c}=\frac{\varepsilon}{4}-\frac{5\varepsilon}{88}>\frac{\varepsilon}{6}.$

That is, $\Pr[E_{k}|G]>\varepsilon/6$ for all $k\in[24/\varepsilon].$ Observe
that the indicator for the event $E_{k}$, for every fixed setting of random
coins (of the algorithm and the adversary) used prior to iteration $k$ of Step
6, is a Bernoulli random variable with the probability parameter equal to the
fraction of sums that are violating and nonerased right before iteration $k$.
Since independent random coins are used in each iteration of Step 6,

$\displaystyle\Pr[\overline{E}|G]\leq\Pr\big{[}\bigcap_{k\in[24/\varepsilon]}\overline{E_{k}}\mid
G\big{]}<(1-\varepsilon/6)^{24/\varepsilon}\leq e^{-4}.$

This yields that $\Pr[E\cap G]>0.7\cdot(1-e^{-4})>2/3$, completing the proof
of the theorem. ∎

###  B.1 Concentration of Pairs that Violate Linearity

In this section, we prove B.2 on the concentration of pairs that violate
linearity. The proof relies on B.4 that gives upper bounds on the fraction of
pairs $(x,y)\in(\\{0,1\\}^{d})^{2}$ that violate linearity and on the fraction
of triples $(x,y,z)\in\\{0,1\\}^{d\times 3}$ such that $(x,y)$ and $(x,z)$
violate linearity. The upper bounds are stated as a function of the distance
to linearity. The distance of a function $f$ to linearity, denoted
$\varepsilon_{f}$, is the minimum over all linear functions $g$ over the same
domain as $f$ of $\Pr_{x}[f(x)\neq g(x)]$.

We remark that a tighter upper bound than Equation 12 in B.4 is shown in [7,
Lemma 3.2]. Since we only need a looser upper bound, we provide a proof for
completeness.

######  Claim B.4.

For all $f\colon\\{0,1\\}^{d}\to\\{0,1\\}$, the following hold:

$\displaystyle\Pr_{x,y\sim\\{0,1\\}^{d}}[(x,y)\textnormal{ violates
linearity}]$ $\displaystyle\leq 3\varepsilon_{f};$ (12)
$\displaystyle\Pr_{x,y,z\sim\\{0,1\\}^{d}}[(x,y)\textnormal{ and
}(x,z)\textnormal{ violate linearity}]$
$\displaystyle\leq\varepsilon_{f}+4\varepsilon_{f}^{2}.$ (13)

###### Proof.

Let $g$ be the closest linear function to $f$. Let $S\subseteq\\{0,1\\}^{d}$
be the set of points on which $f$ and $g$ differ, i.e.,
$S=\\{x\in\\{0,1\\}^{d}\>|\>f(x)\neq g(x)\\}$. Then $|S|=\varepsilon_{f}\cdot
2^{d}$.

For a pair $(x,y)$ to violate linearity, at least one of $x,y$, and $x\oplus
y$ must be in $S$. By a union bound,

$\displaystyle\Pr_{x,y\sim\\{0,1\\}^{d}}[(x,y)\textnormal{ violates linearity
for $f$}]$ $\displaystyle\leq\Pr_{x,y\sim\\{0,1\\}^{d}}[x\in S\vee y\in S\vee
x\oplus y\in S]$ $\displaystyle\leq 3\Pr_{x\sim\\{0,1\\}^{d}}[x\in
S]=3\varepsilon_{f},$

completing the proof of Equation 12.

To prove Equation 13, let $E_{x,y,z}$ be the event that $(x,y)$ and $(x,z)$
violate linearity. By the law of total probability,

$\displaystyle\Pr_{x,y,z\sim\\{0,1\\}^{d}}[E_{x,y,z}]$
$\displaystyle=\Pr[E_{x,y,z}\>|\>x\in S]\Pr[x\in S]+\Pr[E_{x,y,z}\>|\>x\notin
S]\Pr[x\notin S]$ $\displaystyle\leq
1\cdot\varepsilon_{f}+\Pr[E_{x,y,z}\>|\>x\notin S]$
$\displaystyle\leq\varepsilon_{f}+\Pr[(y,z\in S)\vee(x\oplus y,z\in
S)\vee(y,x\oplus z\in S)\vee(x\oplus y,x\oplus z\in S)\mid x\notin S]$
$\displaystyle\leq\varepsilon_{f}+4\Pr[y,z\in S\mid x\notin
S]=\varepsilon_{f}+4\varepsilon_{f}^{2},$

where, in the last line, we used symmetry and a union bound, and then
independence of $x,y$, and $z$. ∎

###### Proof of B.2.

We prove the lemma by applying Chebyshev’s inequality to $Y$. For all
$i,j\in[q]$, where $i<j,$ let $Y_{i,j}$ be the indicator for the event that
$(x_{i},x_{j})$ violates linearity. Then $Y=\sum_{i<j\in[q]}Y_{i,j}$.

First, we obtain a lower bound on $\mathbb{E}[Y]$. By linearity of expectation
and symmetry,

$\mathbb{E}[Y]=\sum_{i<j\in[q]}\mathbb{E}[Y_{i,j}]=\binom{q}{2}\cdot\Pr_{x_{i},x_{j}\sim\\{0,1\\}^{d}}[(x_{i},x_{j})\textnormal{
violates linearity}]\geq\binom{q}{2}\varepsilon_{f},$

where the inequality is due to [7, Theorem 1.2].

Next, we obtain an upper bound on $\text{Var}[Y]$. We have
$\displaystyle\text{Var}[Y]=\sum_{i<j}\text{Var}[Y_{i,j}]+\sum_{\begin{subarray}{c}i<j,k<l\\\
\\{i,j\\}\neq\\{k,\ell\\}\end{subarray}}\text{Cov}[Y_{i,j}Y_{k,l}].$ By
Equation 12, we get
$\text{Var}[Y_{i,j}]\leq\mathbb{E}[Y^{2}_{i,j}]=\mathbb{E}[Y_{i,j}]\leq
3\varepsilon_{f}$. Therefore,

$\sum_{i<j}\text{Var}[Y_{i,j}]\leq 3\binom{q}{2}\varepsilon_{f}.$ (14)

When $\\{i,j\\}\cap\\{k,\ell\\}=\emptyset$, the random variables $Y_{i,j}$ and
$Y_{k,\ell}$ are independent, and thus $\text{Cov}[Y_{i,j}Y_{k,l}]=0$.
Consider the case when $|\\{i,j\\}\cap\\{k,\ell\\}|=1$. Suppose that $i=k$.
Then

$\displaystyle\text{Cov}[Y_{i,j}Y_{i,\ell}]$
$\displaystyle=\mathbb{E}[Y_{i,j}Y_{i,\ell}]-\mathbb{E}[Y_{i,j}]\mathbb{E}[Y_{i,\ell}]\leq\varepsilon_{f}+4\varepsilon_{f}^{2}-\varepsilon_{f}^{2}=\varepsilon_{f}+3\varepsilon_{f}^{2},$

where the inequality follows from Equation 13 and [7, Theorem 1.2]. By
symmetry,

$\sum_{\begin{subarray}{c}i<j,k<l\\\
\\{i,j\\}\neq\\{k,\ell\\}\end{subarray}}\text{Cov}[Y_{i,j}Y_{k,l}]=6\sum_{\begin{subarray}{c}i<j<\ell\end{subarray}}\text{Cov}[Y_{i,j}Y_{i,l}]\leq
6\binom{q}{3}(\varepsilon_{f}+3\varepsilon_{f}^{2})\leq
15\binom{q}{3}\varepsilon_{f},$ (15)

where the last inequality holds since $\varepsilon_{f}\leq\frac{1}{2}$.
Combining Equation 14 with Equation 15, we get that $\text{Var}[Y]\leq
18\binom{q}{3}\varepsilon_{f}.$

Finally, we use $\varepsilon_{f}\geq\varepsilon$, our lower bound on
$\mathbb{E}[Y],$ and Chebyshev’s inequality:

$\displaystyle\Pr\bigg{[}Y\leq{q\choose 2}\frac{\varepsilon}{4}\bigg{]}$
$\displaystyle\leq\Pr\bigg{[}Y\leq{q\choose
2}\frac{\varepsilon_{f}}{4}\bigg{]}\leq\Pr\bigg{[}Y\leq\frac{\mathbb{E}[Y]}{4}\bigg{]}\leq\Pr\bigg{[}\bigg{|}Y-\mathbb{E}[Y]\bigg{|}\geq\frac{3}{4}\cdot{\mathbb{E}[Y]}\bigg{]}$
$\displaystyle\leq\frac{16}{9}\cdot\frac{\text{Var}[Y]}{\mathbb{E}[Y]^{2}}\leq\frac{16\cdot
18}{9}\cdot\frac{\binom{q}{3}\varepsilon_{f}}{\binom{q}{2}^{2}\varepsilon_{f}^{2}}=\frac{16\cdot
18}{9}\cdot\frac{2}{3}\cdot\frac{q-2}{q(q-1)\varepsilon_{f}}<\frac{22}{q\cdot\varepsilon_{f}}=\frac{22\varepsilon}{ct\varepsilon_{f}}\leq\frac{22}{ct}\leq\frac{1}{4},$

since $q=\frac{ct}{\varepsilon}$ and $c=88$. This completes the proof of B.2.
∎