# Investigation of Factorized Optical Flows as Mid-Level Representations

Hsuan-Kung Yang1, Tsu-Ching Hsiao1, Ting-Hsuan Liao1*, Hsu-Shen Liu1*, Li-Yuan
Tsao1*,
Tzu-Wen Wang1*, Shan-Ya Yang1*, Yu-Wen Chen1, Huang-Ru Liao1, and Chun-Yi Lee1
* indicates equal contribution1 Department of Computer Science, National Tsing
Hua UniversityThis work has been submitted to the IEEE for possible
publication. Copyright may be transferred without notice, after which this
version may no longer be accessible.

###### Abstract

In this paper, we introduce a new concept of incorporating factorized flow
maps as mid-level representations, for bridging the perception and the control
modules in modular learning based robotic frameworks. To investigate the
advantages of factorized flow maps and examine their interplay with the other
types of mid-level representations, we further develop a configurable
framework, along with four different environments that contain both static and
dynamic objects, for analyzing the impacts of factorized optical flow maps on
the performance of deep reinforcement learning agents. Based on this
framework, we report our experimental results on various scenarios, and offer
a set of analyses to justify our hypothesis. Finally, we validate flow
factorization in real world scenarios.

##  I Introduction

Combining deep neural networks (DNNs) based perception and control has long
been a crucial research area for a number of robotic application domains, such
as drones [1, 2], self-driving cars [3, 4, 5], robotic arms [6, 7, 8], etc. To
achieve this objective, a branch of researchers [3, 6, 9] adopted end-to-end
learning frameworks, allowing robots to perform actions based on pixels of
high-dimensional, unstructured RGB images. These end-to-end learning
frameworks bypass explicit visual feature learning processes and directly maps
raw visual inputs to robotic actions. However, such end-to-end design lacks
the flexibility of adjusting or fine-tuning, since the perception and control
parts are developed as a whole. In recent years, another branch of researchers
shifted their attention to modular designs, which decompose end-to-end
learning frameworks to perception and control modules, allowing them to be
developed separately. To bridge these modules, appropriate intermediate
feature representations, which are usually referred to as mid-level
representations [10, 11, 12, 13], are used to deliver various types of
information from the perception module to the control module, and form the
basis of modular frameworks for many learning-based systems.

Despite the success of the naive ensemble usage of mid-level representations
[10], nevertheless, the mid-level representations considered in the prior
works usually focus on spatial features extracted from a single frame, and
dedicated little attention to the significance of temporal features concealed
between multiple frames. Although a few researchers [14, 15] proposed to
incorporate optical flow as a type of temporal feature to represent the
displacements of pixels, they overlook the essential properties and
characteristics of optical flows. As a result, such a type of mid-level
representation still leaves room for improvement, since it is unable precisely
describe the temporal information of the objects in a scene.

In light of the above motivations, the main objective of this paper is
twofold. First, we aim to introduce and investigate the concept of flow
factorization, which separates a raw optical flow map into an ego flow map and
an object flow map. An ego flow map is a direct result of the motion of the
viewpoint, and thus provides clues about the translation and rotation of the
viewpoint. On the other hand, an object flow map is caused by the actual
movements of corresponding objects between two different image frames, and
thus can serve as an indicator of the speed and direction of moving objects in
a scene. Since these two types of factorized flow maps bear different physical
meanings, directly leveraging raw flow maps (i.e., the flow maps directly
reflecting the displacements of pixels between two image frames) as a type of
mid-level representation (e.g., [15, 16]) could deliver misleading information
to the control module. We argue that both flow components are necessary and
would contribute to the learning process of the control module, and thus
should be separately treated. The second objective is to investigate the
interplay of factorized flows with the other types of mid-level
representations, and examine the impacts of different compositions of them on
the control module’s performance.

To achieve the above two objectives, we developed a framework for analyzing
and validating the impacts of several most commonly adopted mid-level
representations, including semantic segmentation, depth maps, raw optical flow
maps, as well as factorized flow maps, on the performance of deep
reinforcement learning (DRL) agents. The framework is built atop the Unity
engine [17], and allows DRL agents to be trained to perform collision
avoidance tasks based on a configurable set of mid-level representations. To
investigate the interplay of factorized flows with the other types of mid-
level representations, we designed a diversified set of evaluation scenarios
with different configurations of static and dynamic objects, so as to create
conditions favorable to the agents trained with different types of mid-level
representations. The framework allows its dynamic objects to be configured to
different speeds, such that the speed generalizability of the agents can be
evaluated. The primary contributions include:

  * •

We introduce and investigate a new concept of incorporating factorized flow
maps as mid-level representations.

  * •

We develop a configurable framework along with four different environments for
analyzing the impacts of different compositions of mid-level representations.

  * •

We validate the complementary property of factorized flows with the other
types of mid-level representations.

  * •

We offer a comprehensive set of analyses for the failure cases and the impacts
from changes in frame rates.

  * •

We validate flow factorization in real world scenarios.

##  II Background Material of DRL Based Control

In this section, we briefly review the background of DRL based control method,
which is employed in our framework.

###  II-A Markov Decision Process and Reinforcement Learning

A Markov decision process (MDP) consists of a state space $\mathbb{S}$ that
contains all possible states of an environment $\mathcal{E}$, a primitive
action space $\mathbb{A}$, and a reward function
$\mathcal{R}:\mathbb{S}\times\mathbb{A}\to\mathbb{R}$. In an MDP, an agent
perceives a state $s_{t}\in\mathbb{S}$, takes an action $a_{t}\in\mathbb{A}$
according to its control policy $\pi:\mathbb{S}\to\mathbb{A}$, receives a
reward $r_{t}=\mathcal{R}(x_{t},a_{t})$, and then transitions to a next state
$s_{t+1}$ determined by $\mathcal{E}$ at each discrete timestep $t$.

The objective of reinforcement learning (RL) [18, 19] is to search for an
optimal policy $\pi^{*}$ in $\mathcal{E}$ characterized by an MDP. An RL-based
agent performs episodes of a task and iteratively updates its $\pi$ to search
for $\pi^{*}$ via collections of transition record
$(s_{t},a_{t},r_{t},s_{t+1})$, where $\pi^{*}$ maximizes the expected return
$G_{t}=\mathbb{E}\big{[}\sum^{T}_{\tau=t}\gamma^{\tau-t}r_{\tau}\big{]}$
within an episode. The discount factor $\gamma$ represents the agent’s extent
of preference for short-term or long-term rewards. The horizon $T$ stands for
the length of one episode in $\mathcal{E}$. In recent years, RL algorithms
based on DNNs, which are commonly referred to as DRL, have attracted the
attention of researchers due to the fact that DRL can handle high-dimensional
state spaces, e.g., the mid-level representations considered by this work [20,
21].

###  II-B Maximum Entropy RL and Soft Actor-Critic

To enhance the exploration behaviors of RL agents, maximum entropy RL [22]
proposes to find a $\pi$ that maximizes the expected return along with the
entropy of $\pi$, given by:

$G_{t}=\mathbb{E}[\sum^{T}_{\tau=t}\gamma^{\tau-t}(r_{\tau}+\alpha\mathcal{H}(\pi))],$
(1)

where $\mathcal{H}(\pi)\triangleq\mathbb{E}[-\log\pi(\cdot|s_{t})]$ denotes
the entropy of the policy, and $\alpha$ is a temperature parameter, which
controls the contribution of the entropy term to $G_{t}$. Based on this
concept, soft actor-critic (SAC) [23, 24] further introduces a new model-free
learning framework, which integrates a parameterized soft-Q function
$Q_{\theta}$ and a parameterized stochastic policy $\pi_{\phi}$, where
$\theta$ and $\phi$ denote the weights of DNNs. SAC achieves the state-of-the-
art results on several benchmarks [25] for continuous control tasks. The
weights $\theta$ and $\phi$ are trained by iteratively minimizing the
objective functions $J_{Q}(\theta)$ and $J_{\pi}(\phi)$ respectively,
formulated as:

$\displaystyle
J_{Q}(\theta)=\mathbb{E}_{s_{t},a_{t}}\left[\frac{1}{2}(Q_{\theta}(s_{t},a_{t})-(r(s_{t},a_{t})+\gamma\mathbb{E}_{s_{t+1}\sim
p}[V(s_{t+1})]))^{2}\right],$

(2)
$J_{\pi}(\phi)=\mathbb{E}_{s_{t}}[\mathbb{E}_{a_{t}\sim\pi_{\phi}}[\alpha\log(\pi_{\phi}(a_{t}|s_{t}))-Q_{\theta}(s_{t},a_{t})]],$
(3)

where $V(s_{t})$ denotes the soft state value function, given by:

$V(s_{t})=\mathbb{E}_{a_{t}\sim\pi_{\phi}}[Q_{\theta}(s_{t},a_{t})-\alpha\log\pi_{\phi}(a_{t}|s_{t})].$
(4)

While searching for a proper $\alpha$ is not straightforward, [24] automates
this process by training $\alpha$ to minimize $J(\alpha)$:

$J(\alpha)=\mathbb{E}_{a_{t}\sim\pi_{\phi}}[-\alpha\log\pi_{\phi}(a_{t}|s_{t})-\alpha\mathrm{bar}{\mathcal{H}}],$
(5)

where $\mathrm{bar}{\mathcal{H}}$ is the target entropy (a hyperparameter). In
addition to the continuous action space setup, the authors in [26] also
extended SAC [24] to discrete action settings by exchanging the Gaussian
distribution of the stochastic policy with a Softmax distribution. The authors
in [27] further extends SAC to a hybrid control (i.e., continuous and
discrete) domain.

##  III Preliminaries of Mid-Level Representations

In this section, we first introduce the concepts of mid-level representations,
and then discuss the properties for several types of mid-level representations
considered in this work. The mid-level representations discussed in this
section, along with the factorized flow components introduced in Section IV,
are all incorporated into the framework presented in Section V for inspecting
the impacts of them on the control module.

###  III-A Definition

Mid-level representations are specific abstractions reflecting different
physical or semantic meanings, and are usually bearing domain-invariant
properties that are usually measured, inferred, or extracted from various
kinds of visual scenes. Due to these characteristics, several types of mid-
level representations, such as semantic segmentation, depth map, and raw
optical flow, have long been utilized to transfer information from the
perception modules to the control modules for several robotic applications
[28, 29]. Since different types of mid-level representations have their own
strengths and weaknesses in different scenarios, a comprehensive understanding
of mid-level representations, therefore, are especially crucial to the final
success of modular learning-based frameworks.

###  III-B Properties of Mid-Level Representations

In this subsection, we discuss the key properties of several commonly adopted
mid-level representations, and elaborate on the advantages and primary
limitations of them.

##### Semantic segmentation ($\mathcal{S}$)

Semantic segmentation is a type of representation generated by clustering
parts of an image together which belong to the same object class. It is a form
of pixel-level prediction because each pixel in an image is classified
according to a category. Semantic segmentation has received great attention by
robotic and computer vision researchers over decades due to its capability to
easily convey semantic meanings of images from a perception to a control
modules. Despite the convenience, its main drawback is that it is unable to
reveal information about the relative positions and motions between two
different objects in the spatial domain.

##### Depth map ($\mathcal{D}$)

A depth map is an image or an image channel that contains information relating
to the distances of the surfaces of scene objects from a viewpoint. A depth
map can be either measured by physical sensors (e.g., lidars, ultrasonic
sensors, infrared sensors, etc.), or be estimated from image frames by
computer vision based techniques. Depth maps are used in a wide range of
robotic domains, as they reveal the spatial distances of objects in a scene.
Nevertheless, depth maps are difficult to extract full semantic clues.
Besides, similar to $\mathcal{S}$, they inherently do not contain the motion
information of the observed objects and the viewpoint.

##### Raw optical flow map ($\mathcal{F}_{raw}$)

Optical flow estimation is a technique for evaluating the motion of objects
between consecutive images, which typically requires a reference image and a
target image. Optical flow is usually represented as a vector field containing
displacement vectors assigned to the pixels of the reference image. These
vectors indicate the shifts of the corresponding pixels from the target image,
and can be exploited to represent the motion features of a scene. An optical
flow map directed estimated from two image frames is referred to as a raw
optical flow map ($\mathcal{F}_{raw}$), which contains the flow components
caused by the moving objects in a scene as well as the flow components caused
by the motion of the viewpoint. Except for the above information, a raw
optical flow map also implicitly encodes certain extents of depth information,
as the magnitudes of the optical flows from an object is related to its
distance from the viewpoint. Similar to $\mathcal{D}$, $\mathcal{F}_{raw}$
also does not offer explicit semantic information, and thus is rarely used
alone in modular frameworks. Moreover, it is difficult to distinguish the two
different sources of the flow components concealed in $\mathcal{F}_{raw}$, and
leverage them to assist the control of a robot.

##  IV Optical Flow Factorization

In this section, we introduce the concept of optical flow factorization,
discuss the motivation of employing factorized flow components as mid-level
representations, and then describe the problem formulation and the
factorization procedure.

Figure 1: A visualization of flow factorization. A raw flow map
($\mathcal{F}_{raw}$) can be factorized into an ego flow map
($\mathcal{F}_{ego}$) and an object flow map ($\mathcal{F}_{obj}$). The colors
presented in the flow maps are drawn based on the directional color-coding as
shown at the top-right corner. The vector at each pixel coordinate corresponds
to a certain flow direction and magnitude.

###  IV-A Concept and Motivation

As discussed in Section I, one of the primary objectives of this paper is to
investigate the influences of incorporating factorized flow components as mid-
level representations. In light of the limitation of $\mathcal{F}_{raw}$
discussed in Section III, we propose to further factorize it into two
constituent flow fields, which are referred to as ego flow map
($\mathcal{F}_{ego}$) and object flow map ($\mathcal{F}_{obj}$), respectively.
The former reflects the portion of $\mathcal{F}_{raw}$ caused by the motion of
the viewpoint, while the latter corresponds to the rest portion of
$\mathcal{F}_{raw}$ caused by the motion of the observed objects. Such a
factorization allows $\mathcal{F}_{ego}$ and $\mathcal{F}_{obj}$ to explicitly
represent specific physical meanings, and thus enhances the expressiveness
when optical flow is intended to be utilized as a type of mid-level
representation.

Fig. 1 illustrates a motivational example of optical flow factorization. In
this example, the viewpoint is moving forward, while the pedestrian closest to
the viewpoint is moving to the right. In the leftmost subfigure, the raw flow
field within that pedestrian region is composed of displacement vectors
pointing to multiple directions (i.e., represented in terms of different
colors) due to the different moving directions of the viewpoint and the
pedestrian. When the raw flow field is factorized into $\mathcal{F}_{ego}$ and
$\mathcal{F}_{obj}$, as depicted on the right-hand side of Fig. 1, the flow
fields within the pedestrian region become consistent in both of them. This
example implies that simply leveraging $\mathcal{F}_{raw}$ as the mid-level
representation might lead to ambiguity for interpreting the motions of the
objects in a scene. On the other hand, $\mathcal{F}_{ego}$ and
$\mathcal{F}_{obj}$ clearly reflects the true motions of the viewpoint and the
pedestrian, and thus can serve as more expressive mid-level representations.
To the best of our knowledge, the existing off-the-shelf simulators are unable
to offer $\mathcal{F}_{ego}$ and $\mathcal{F}_{obj}$ as mid-level
representations in a straightforward manner, if without further post
processing or modification of them.

Figure 2: An overview of our framework, which allows incorporation and
modification of environments, mid-level representations, scenarios, as well as
DRL algorithms. Based on the given configuration, a set of mid-level
representations are allowed to be selected from
$\\{\mathcal{S},\mathcal{D},\mathcal{F}_{raw},\mathcal{F}_{ego},\mathcal{F}_{obj}\\}$,
and form the state space $\mathbb{S}$ for the agent to learn a $\pi$ in a
designated environment.

###  IV-B Problem Formulation and Factorization Procedure

In this subsection, we formulate the optical flow factorization problem in
mathematical equations, and explain its procedure. As defined in Section III,
an optical flow map is a vector field containing displacement vectors
corresponding to the pixels between two image frames. For a certain pixel
$\mathbf{p}_{t}$ of an image at timestep $t$, its corresponding raw optical
flow can be denoted as a vector $\mathbf{f}^{t}_{raw}\in\mathcal{F}_{raw}$,
expressed as:

$\mathbf{f}^{t}_{raw}=\mathbf{f}^{t}_{obj}+\mathbf{f}^{t}_{ego},$ (6)

where $\mathbf{f}^{t}_{obj}\in\mathcal{F}_{obj}$ and
$\mathbf{f}^{t}_{ego}\in\mathcal{F}_{ego}$ represent the component vectors
caused by the motions of the object and the viewpoint, respectively. The
procedure of decomposing $\mathbf{f}^{t}_{raw}$ into $\mathbf{f}^{t}_{obj}$
and $\mathbf{f}^{t}_{ego}$ at each pixel coordinate of an image is called flow
factorization. To perform the procedure, we start with the definition of
$\mathbf{f}^{t}_{ego}$. Let $\mathbf{p}_{t}=(x_{t},y_{t})$ be the pixel
coordinate at timestep $t$, and
$\mathbf{p}_{t^{\prime}}=(x_{t^{\prime}},y_{t^{\prime}})$ be the projected
pixel coordinate of the same three dimensional point corresponding to
$\mathbf{p}_{t}$ but perceived from the viewpoint at a prior timestep
$t^{\prime}$, $\mathbf{f}^{t}_{ego}$ can be derived from the following
equation:

$\mathbf{f}^{t}_{\text{ego}}=\frac{\mathbf{p}_{t}-\mathbf{p}_{t^{\prime}}}{\Delta
t},$ (7)

where $\Delta t=t-t^{\prime}$ denotes the time difference. Nevertheless,
$\mathbf{p}_{t^{\prime}}$ is unknown in advance, and has to be inferred from
the correspondence between $\mathbf{p}_{t}$ and $\mathbf{p}_{t^{\prime}}$.
Given the current pixel coordinate $\mathbf{p}_{t}$, the rotation and
translation matrices of the viewpoint $\mathbf{R}_{3\times 3}$ and
$\mathbf{T}_{3\times 1}$, the real depth value $Z_{t}$, and the camera
intrinsic parameters $\\{f,c_{x},c_{y}\\}$, the correspondence between
$\mathbf{p}_{t}$ and $\mathbf{p}_{t^{\prime}}$ can be established based on the
approach similar to [30]. To derive $\mathbf{p}_{t^{\prime}}$,
$\mathbf{p}_{t}$ is first utilized to calculate the three dimensional
coordinate of the viewpoint. The pinhole camera model describes the
transformation between pixel and viewpoint coordinates as a linear mapping in
homogeneous coordinates, which is formulated as the following:

$\begin{bmatrix}x_{t}\\\ y_{t}\\\ 1\end{bmatrix}=\begin{bmatrix}f&0&c_{x}&0\\\
0&f&c_{y}&0\\\ 0&0&1&0\end{bmatrix}\begin{bmatrix}X_{t}\\\ Y_{t}\\\ Z_{t}\\\
1\end{bmatrix},$ (8)

where $(X_{t},Y_{t},Z_{t})$ is the three dimensional coordinate of the
viewpoint, $f$ the focal length, and $(c_{x},c_{y})$ the principal point. The
mappings of the two coordinates can be derived as:

$x_{t}=f\frac{X_{t}}{Z_{t}}+c_{x},\quad y_{t}=f\frac{Y_{t}}{Z_{t}}+c_{y},$ (9)
$X_{t}=\frac{Z_{t}}{f}(x_{t}-c_{x}),\quad Y_{t}=\frac{Z_{t}}{f}(y_{t}-c_{y}).$
(10)

The viewpoint coordinate of $\mathbf{p}_{t^{\prime}}$ can be derived by
applying the transform of the viewpoint using $\mathbf{R}_{3\times 3}$ and
$\mathbf{T}_{3\times 1}$ as:

$\begin{bmatrix}X_{t^{\prime}}\\\ Y_{t^{\prime}}\\\ Z_{t^{\prime}}\\\
1\end{bmatrix}=\begin{bmatrix}\mathbf{R}_{3\times 3}&\mathbf{T}_{3\times 1}\\\
\mathbf{0}&1\end{bmatrix}\begin{bmatrix}X_{t}\\\ Y_{t}\\\ Z_{t}\\\
1\end{bmatrix}.$ (11)

Finally, $\mathbf{p}_{t^{\prime}}$ can be derived from (9), and
$\mathbf{f}^{t}_{\text{ego}}$ can be calculated from (7). Typically,
$\mathbf{f}^{t}_{raw}$ can be obtained from the shader of a simulation engine,
or evaluated from raw RGB images by conventional flow estimation approaches.
As a result, $\mathbf{f}^{t}_{obj}$ can be obtained by subtracting
$\mathbf{f}^{t}_{ego}$ from $\mathbf{f}^{t}_{raw}$. By applying the above flow
factorization procedure to all the pixel coordinates of an image,
$\mathcal{F}_{raw}$ can be factorized into $\mathcal{F}_{ego}$ and
$\mathcal{F}_{obj}$.

Figure 3: An overview of the environments designed for our experiments. The
green and red lines represent the walking paths of the pedestrians. The
corresponding green and red suits denote the starting and ending zones of
different paths, respectively.

##  V Framework

###  V-A Design Philosophy of the Framework

In order to validate our assumption that $\mathcal{F}_{ego}$ and
$\mathcal{F}_{obj}$ are promising candidates for mid-level representations, we
develop a configurable framework based on the Unity engine [17] and the Unity
ML-Agents Toolkit [31]. The framework is designed with an aim to facilitate
the incorporation and modification of environments, scenarios, mid-level
representations, as well as DRL algorithms. Such a design philosophy allows us
to fulfill our objective of investigating the impacts of $\mathcal{F}_{ego}$
and $\mathcal{F}_{obj}$ under different conditions, and examine the interplay
of them with the other types of mid-level representations. In this framework,
the inputs to the DRL agents (i.e., mid-level representations) are all high-
dimensional. As a result, the agents are required to interpret the provided
mid-level representations, and extract necessary information concealed in them
to learn its policy $\pi$. Please note that optical flow factorization is not
a built-in feature of the Unity engine, and is completely developed by
ourselves.

###  V-B Workflow of the Framework

Fig. 2 illustrates an overview of the framework. To validate the framework,
the raw RGB image observations of the environment from the viewpoint of the
camera mounted on the agent are all transformed to mid-level representations
by the built-in renderer. The shader offers five different types of mid-level
representations that are discussed in Sections III-B and IV. For each round of
simulation, an environment (i.e., $\mathcal{E}$) along with a set of mid-level
representations that form the state space (i.e.,
$\mathbb{S}\subseteq\\{\mathcal{S},\mathcal{D},\mathcal{F}_{raw},\mathcal{F}_{ego},\mathcal{F}_{obj}\\}$)
are selected to train an DRL agent. Different compositions of mid-level
representations can be configured as $\mathbb{S}$. At each timestep $t$, an
observed state $s_{t}\in\mathbb{S}$ is fed into the DRL agent as its input
observation. The feature embeddings of different mid-level representations are
extracted by different CNNs that belong to the agent’s model, and are then
concatenated together for the policy of the agent to determine an action to be
performed. The environments in the framework contain multiple static objects
(cars, trees, buildings, etc.) as well as dynamic objects (i.e., road crossing
pedestrians), where the speeds and moving directions of the dynamic objects
are fully configurable. The agent is trained with a reward function defined in
the framework, with an aim to learn to successfully navigate to the designated
ending zone(s) (as denoted in Fig. 3), without colliding with any other
objects (either static or dynamic) in the environment.

##  VI Experimental Results

In this section, we present the experimental setups, the quantitative and
qualitative results, and a set of analyses.

###  VI-A Experimental Setup

####  VI-A1 Environmental Setup

To evaluate the impacts of mid-level representations, we carefully designed
four different environments based on urban scenes. These environments are
crafted to reflect multiple different realistic scenarios. The scenarios which
are considered in this work span over Straight Road, S-Turn, H-Shaped
Pathways, as well as Three-Way Junction. The four environments are illustrated
in Fig. 3, and are described in the following paragraphs. The detailed
configurations of these environments are presented in Table I.

##### Straight Road

The Straight Road environment is the simplest one-way road with several
pedestrian groups crossing the road. The agent has to move on the road,
avoiding the pedestrians, and not hitting any sidewalks and buildings.

##### S-Turn

The S-Turn environment features an s-shaped path in which the agent has to
learn to keep making turns in correct directions while avoiding any obstacles
in it. If there is no explicit semantic information, it will be difficult for
the agent to move correctly on the road region. As a result, using either raw
optical flow map or depth map would be disadvantageous for the agent to
navigate to the ending zone.

##### H-Shaped Pathways

The H-Shaped Pathways environment is even more difficult than the previous
two, and features two intersections as well as randomly selected navigation
path from four possible ones. In addition, the environment contains static
pedestrians and dynamic pedestrians. As a result, if the agent only detects
semantic information, it will be difficult for the agent to be aware of
whether the pedestrians are moving or not. The mechanism of randomly selecting
the navigation path at each episode is included to test if the agent overfits.
Besides, the directions of moving pedestrians might be perpendicular or
parallel to the direction of the agent.

##### Three-Way Junction

The Three-way Junction is designed for evaluating the agent’s capability for
making either left or right turns, which is considered to be more complicated
than Straight Road. The T-shaped design aims to prevent the agent from over-
fitting on any specific turn direction. The environment contains more types of
obstacles, including terrains, trees, fences, cars parked on the roadsides,
traffic lights, and so on. The directions of the moving pedestrians are
designed to be parallel to the agent’s path.

TABLE I: The detailed setups of the four environments.

Environment | Straight Road | S-Turn | H-Shaped Pathways | Three-Way Junction
---|---|---|---|---
Time limit $T$ (timesteps) | 200 | 250 | 300 | 250
Paths | $1$ | $2$ | $4$ | $2$
Lane width | $2$ | $1.5$ | $2$ | $1$
Object categories | $5$ | $6$ | $7$ | $11$
Turns | ✗ | ✓ | ✓ | ✓
Pedestrian (dynamic, perpendicular) | ✓ | ✓ | ✓ | ✗
Pedestrian (dynamic, parallel) | ✗ | ✗ | ✓ | ✓
Pedestrian (static) | ✗ | ✗ | ✓ | ✗
Obstacles (static) | ✗ | ✗ | ✗ | ✓

TABLE II: The hyperparameters used for the SAC algorithm.

Parameter | Value | Parameter | Value
---|---|---|---
Optimizer | Adam | Number of hidden layers | $1$
Learning rate | $3\cdot 10^{-4}$ | Number of hidden units per layer | $512$
Learning rate schedule | linear | Steps per update | $10$
Initial entropy coefficient | $0.5$ | Training steps | $2\cdot 10^{6}$
Replay buffer size | $10,240$ | Target entropy | $0.2\cdot\log{\text{dim}(\mathbb{A})}$
Batch size | $1,024$ |  |

Figure 4: An impact analysis of the composition of the flow maps. The agents
are trained using the normal speed mode ($1.2\sim 1.8$ m/s), and evaluated
under the low speed mode ($0.6\sim 1.0$ m/s) and the high speed mode ($2.0\sim
2.4$ m/s).

####  VI-A2 Setup of the RL Agent

We next describe the setup of the RL agent. At the beginning of each episode,
an RL agent implemented as a DNN is trained by the SAC algorithm. The training
process of the agent is completely carried out in one of the four environments
(i.e., $\mathcal{E}$), and the policy $\pi$ of the agent is updated in each
episode. Within an episode, the agent interacts with $\mathcal{E}$, and
receives the rewards at each timestep $t$, where the collision oracle can be
obtained via the built-in physic engine. An episode terminates when the agent
reaches the ending zone, or exceeds the time limit $T$ of $\mathcal{E}$.

##### Reward Function

In our experiments, we use the simplest reward model which only provides the
minimal learning signal essential for the agents to accomplish the tasks.
Specifically, the agent receives $5.0$ when reaching the ending zone, and
$-5.0$ if the agent failed due to either colliding with obstacles, moving out
of the bounds, or exceeding the time limit. We use $0.01$ as the survival
bonus for every timestep.

##### Action Space

The action space $\mathbb{A}$ of the agent consists of three discrete actions,
and is formulated as
$\mathbb{A}=\small{\\{}\texttt{NO\\_OP},\texttt{TURN\\_LEFT}(\alpha),\texttt{TURN\\_RIGHT}(\alpha)\small{\\}}$,
where $\alpha$ is the angular acceleration. We use
$\alpha=35\mathrm{\SIUnitSymbolDegree}\mathrm{/}\mathrm{s}^{2}$ in the
Straight Road environment, and
$\alpha=70\mathrm{\SIUnitSymbolDegree}\mathrm{/}\mathrm{s}^{2}$ for the
others. A constant forward speed $v=10\mathrm{m}\mathrm{/}\mathrm{s}$ is
consistently applied to the agent.

####  VI-A3 Hyper-Parameter Setup

We employ the feature encoder of [32] to encode each mid-level representation
into an embedding. The embeddings are then concatenated and passed to the
agent’s value and policy networks for predictions, which are linear layers
with the size equal to the action space. The detailed hyper-parameter settings
are summarized in Table II.

###  VI-B Impact Analysis of the Composition of the Flow Maps

Based on the framework presented in Section V, we first analyze the impacts of
different compositions of the flow maps, including $\mathcal{F}_{ego}$,
$\mathcal{F}_{obj}$, $\mathcal{F}_{raw}$, and
$\mathcal{F}_{ego}+\mathcal{F}_{obj}$, on the success rates of the DRL agents
trained in the four environments discussed in the previous section, where
‘$\mathcal{F}_{ego}+\mathcal{F}_{obj}$’ denotes that the feature embeddings of
$\mathcal{F}_{ego}$ and $\mathcal{F}_{obj}$ are extracted by CNNs and then
concatenated as two distinct channels. We design three different non-
overlapping speed configurations for the road-crossing pedestrians (i.e.,
dynamic objects): (a) low speed mode ($0.6\sim 1.0$ m/s), (b) normal speed
mode ($1.2\sim 1.8$ m/s), and (c) high speed mode ($2.0\sim 2.4$ m/s). For
each mode, the pedestrians are randomly assigned a moving speed within the
designated speed range. The agents are trained using the normal speed mode,
and are evaluated either under the low speed mode or the high speed mode. Fig.
4 depicts the evaluation results. The observations and insights from it are
discussed in the following paragraphs.

#####  $\mathcal{F}_{ego}$ is beneficial for the low speed mode, but is
insufficient for the high speed mode

From Fig. 4, it is observed that the agents trained with only
$\mathcal{F}_{ego}$ usually deliver satisfying performance when the
pedestrians move slowly (i.e., the entire scene is relatively static). The
rationale is that, under such circumstances, the agents could comprehend and
explore the scenes by focusing only on the flows caused by the motions of the
viewpoint. In other words, when the objects are all nearly static,
$\mathcal{F}_{ego}$ provides the agents an easier way to capture the relative
locations between it and its surrounding objects, thus allows the agent to
avoid colliding with them. For example, when the vectors in
$\mathcal{F}_{ego}$ point to the left, it suggests that the viewpoint is
moving or turning to the right, where the magnitudes of the vectors in
$\mathcal{F}_{ego}$ reflect the relative distances of the objects to the
viewpoint. This also reveals that, by observing $\mathcal{F}_{ego}$, the
agents could also learn the causal relationship between its taken action and
the flow field it incurs. This, in turn, allows it to further re-adjust its
next action based on the observed $\mathcal{F}_{ego}$. Although the
experimental evidences suggest that the agents can benefit from
$\mathcal{F}_{ego}$ in nearly static settings, however, Fig. 4 also reveals
that the performance of the agents drop when fast moving objects exist (i.e.,
in the high speed setup). This is due to the fact that $\mathcal{F}_{ego}$
does not offer any clue about moving objects. Please note that in the Three-
way Junction, the performance of the agent does not degrade significantly in
high speed mode. This is because the moving objects in this environment only
move toward or away from the agent, and thus sufficiently allows it to avoid
them based on $\mathcal{F}_{ego}$.

#####  $\mathcal{F}_{raw}$ is mostly dominated by $\mathcal{F}_{ego}$

In S-Turn, H-Shape Pathways, and Three-way Junction, it can be observed that
the agents trained with $\mathcal{F}_{raw}$ perform similar to those trained
with $\mathcal{F}_{ego}$ under the low speed mode. For this observation, our
hypothesis is that when being fed with $\mathcal{F}_{raw}$, it could be
difficult for the agents to distinguish the flows caused by the motions of the
viewpoint and the moving objects. A possible explanation is that
$\mathcal{F}_{obj}$ only takes up a small portion of $\mathcal{F}_{raw}$ in
most cases. As a result, $\mathcal{F}_{raw}$ is usually dominated by
$\mathcal{F}_{ego}$, as depicted in Fig. 1. However, the results in Fig. 4
suggest that the agents trained with $\mathcal{F}_{raw}$ still benefit from
the hidden information that comes from the object motions, and achieve better
performance than the agents trained with $\mathcal{F}_{ego}$ only in Straight
Road, S-Turn, and H-Shaped Pathways under the high speed mode. This implies
that the flows caused by the objects still plays an non-negligible role in the
high speed mode. Please note that the performance under the high speed mode in
the Three-way Junction does not follow the same trend as the other
environments. This is because the moving directions of the objects are mostly
parallel to the moving direction of the agent. Therefore, the contributions
from $\mathcal{F}_{obj}$ becomes relatively insignificant in this environment.

#####  $\mathcal{F}_{ego}+\mathcal{F}_{obj}$ are crucial for speed
generalization

In can be observed from Fig. 4 that the agents trained with
$\mathcal{F}_{ego}+\mathcal{F}_{obj}$ achieve much balanced performance in
both the low speed and the high speed modes, and are able to outperform the
agents trained with the other flow compositions in all of the four
environments when evaluated under the high speed mode. This validates our
hypothesis that flow factorization is crucial for interpreting the motions in
a scene, and is beneficial to the scene understanding of the agents.

Figure 5: The experimental results for validating the complementary property
of the factorized flow maps (i.e., $\mathcal{F}_{ego}+\mathcal{F}_{obj}$).

###  VI-C The Complementary Property of the Factorized Flows

Based on the previous observations and insights, we next examine whether the
factorized flow maps, i.e., $\mathcal{F}_{ego}+\mathcal{F}_{obj}$, can be used
together with the other types of mid-level representations to further enhance
the performance of the DRL agents. In order to inspect if this complementary
property exists, we next present an experiment for comparing the influences of
the following compositions of mid-level representations on the DRL agents:
$\\{\mathcal{S}_{2},\mathcal{D}_{2},\\{\mathcal{F}_{ego},\mathcal{F}_{obj}\\},\\{\mathcal{F}_{ego},\mathcal{F}_{obj},\mathcal{S}_{2}\\},\\{\mathcal{F}_{ego},\mathcal{F}_{obj},\mathcal{D}_{2}\\},\\\
\\{\mathcal{F}_{ego},\mathcal{F}_{obj},\mathcal{S}_{2},\mathcal{D}_{2}\\}\\}$,
where $\mathcal{S}_{2}$ and $\mathcal{D}_{2}$ denote that two consecutive
semantic segmentation and depth maps are stacked, respectively. Such a setup
ensures that $\mathcal{S}_{2}$, $\mathcal{D}_{2}$, and
$\\{\mathcal{F}_{ego},\mathcal{F}_{obj}\\}$ are all derived on the basis of
two consecutive raw RGB image frames. The above compositions are designed
based on the insight from Section VI-B that combined usage of
$\mathcal{F}_{ego}+\mathcal{F}_{obj}$ delivers the best results in the high
speed mode, and satisfying performance in the low speed mode.

Fig. 5 plots the results of this experiment. It can be observed that the
agents trained with $\mathcal{F}_{ego}+\mathcal{F}_{obj}$ outperform those
trained without them in all of the environments, suggesting the existence of
the complementary property of $\mathcal{F}_{ego}+\mathcal{F}_{obj}$ with
$\mathcal{S}_{2}$ or $\mathcal{D}_{2}$. Another interesting observation from
Fig. 5 is that augmenting $\mathcal{F}_{ego}+\mathcal{F}_{obj}$ with both
$\mathcal{S}_{2}$ and $\mathcal{D}_{2}$ also provides positive impact on the
performance of the agents. The performance boost, in our opinion, comes from
the awareness of semantic information contributed by $\mathcal{S}_{2}$ as well
as the distance information provided by $\mathcal{D}_{2}$. The experimental
evidences therefore suggest that $\mathcal{F}_{ego}+\mathcal{F}_{obj}$ and the
other mid-level representations can be utilized together, and deliver even
better performance than using either of them alone. It is also worth noting
that the agents trained with
$\\{\mathcal{S}_{2},\mathcal{D}_{2},\mathcal{F}_{ego},\mathcal{F}_{obj}\\}$ do
not always deliver the highest success rates. A more complicated DNN
architecture design or a more sophisticated training methodology might be
necessary to enable the agents to digest and leverage the rich spatial and
temporal information contained in these mid-level representations.

###  VI-D Failure Case Analysis

TABLE III: The breakdowns of the causes of the failure cases for two different
types of failures, including (1) out-of-bound (OOB) and (2) collision, in the
S-Turn environment.

Mid-level Representations | Causes of the Failure Cases
---|---
| OOB | Collision | OOB-to-collision ratio
$\mathcal{F}_{ego}$ \+ $\mathcal{F}_{obj}$ | 12.82% | 87.18% | 0.147
$\mathcal{D}_{2}$ | 9.51% | 90.49% | 0.105
$\mathcal{S}_{2}$ | 4.47% | 95.53% | 0.047
$\mathcal{F}_{ego}$ \+ $\mathcal{F}_{obj}$ \+ $\mathcal{D}_{2}$ | 8.05% | 91.95% | 0.088
$\mathcal{F}_{ego}$ \+ $\mathcal{F}_{obj}$ \+ $\mathcal{S}_{2}$ | 2.72% | 97.28% | 0.028
$\mathcal{F}_{ego}$ \+ $\mathcal{F}_{obj}$ \+ $\mathcal{D}_{2}$ \+ $\mathcal{S}_{2}$ | 3.20% | 96.80% | 0.033

To further investigate the impacts of $\mathcal{F}_{ego}+\mathcal{F}_{obj}$ as
well as the other compositions of mid-level representations, we next look into
the failure cases and analyze the causes of them. Table III reports the
breakdowns of the causes of the failure cases, including (1) out-of-bound
(OOB) and (2) collision. The former corresponds to the cases that the agents
touch or cut into illegal regions (e.g., sidewalks), while the latter
represents the cases that the agents collide with road-crossing pedestrians.
The percentages in Table III reveal that for all the cases, collision account
for the majority of the failures. For the case of
$\mathcal{F}_{raw}+\mathcal{F}_{ego}$, the percentage of OOB is higher than
that of the other cases, as flow maps are unable to provide sufficient
semantic information to distinguish the difference between roads and
sidewalks. The agents solely trained with $\mathcal{D}_{2}$ also face similar
issues. On the other hand, the percentage of OOB is much lower for the
$\mathcal{S}_{2}$ case, since semantic segmentation explicitly informs the
agent about the boundaries of roads. When semantic segmentation is consider
together with factorized flow maps (i.e.,
$\mathcal{F}_{raw}+\mathcal{F}_{ego}+\mathcal{S}_{2}$), the percentage of OOB
is reduced by a significant margin. The above failure analysis thus validates
that different mid-level representations bear different properties, and have
different influences on the behavior and performance of the agents.

Figure 6: The performance sensitivity to the changes in FPS.

###  VI-E Analysis of Sensitivity to Frame Rates

As optical flow maps, $\mathcal{S}_{2}$, and $\mathcal{D}_{2}$ are obtained
from two image frames, we next examine whether the time interval between these
two frames would affect the performance of the agents. Since optical flow maps
reflect the displacements of pixels between two different frames, the length
of the time interval between them would directly affects the magnitudes and
directions of the derived flow vectors. Any changes in this time interval
would also cause $\mathcal{S}_{2}$ and $\mathcal{D}_{2}$ to be different. As a
result, in this section, we further investigate on the impact of that time
interval on the agents’ performance under different compositions of mid-level
representations. The results are depicted in Fig. 6, where the time interval
is reflected in the form of frames per second (FPS). The agents are trained
with the frame rate set to $12$ FPS, and are evaluated using $6\sim 10$ FPS
under the normal speed mode. The results in Fig. 6 indicate that for all
different compositions of mid-level representations, the performances of the
agents decrease as the FPS used for evaluation decreases. The results also
show that the agents trained with $\mathcal{F}_{ego}+\mathcal{F}_{obj}$ are
more sensitive to the time interval than those trained with either
$\mathcal{S}_{2}$ or $\mathcal{D}_{2}$. This can be attributed to the fact
that flow maps directly encode the displacements of pixels into vectors, and
thus might cause the agents to suffer from larger changes in their input
observations as the time interval increases. On the other hand, the agents
trained with $\mathcal{S}_{2}$ or $\mathcal{D}_{2}$ are less sensitive to the
changes in the time interval, since the stacked frames might still be similar
to each other and have large overlapped areas. Although the agents trained
with $\mathcal{F}_{ego}+\mathcal{F}_{obj}$ suffer from larger performance
drop, it still achieves similar performance to those trained with
$\mathcal{S}_{2}$ or $\mathcal{D}_{2}$ when the FPS is decreased to $6$. It is
also worth noting that the agents trained with
$\\{\mathcal{F}_{ego},\mathcal{F}_{obj},\mathcal{S}_{2}\\},\\{\mathcal{F}_{ego},\mathcal{F}_{obj},\mathcal{D}_{2}\\}$,
and
$\\{\mathcal{F}_{ego},\mathcal{F}_{obj},\mathcal{S}_{2},\mathcal{D}_{2}\\}$
only degrade slightly, as the agents may benefit from the complementary
property discussed above.

Figure 7: Real world demonstration of flow factorization.

###  VI-F Real World Validation of Flow Factorization

In this section, we demonstrate flow factorization in the real world
scenarios. We generate $\mathcal{F}_{raw}$ by the RAFT flow predictor [33],
obtain $Z$, $\mathbf{R}_{3\times 3}$, and $\mathbf{T}_{3\times 1}$ from the
ZED 2i camera [34], and perform the flow factorization procedure discussed in
Section IV. The results are depicted in Fig. 7, in which two scenarios with
different $\mathcal{F}_{raw}$ are shown in Fig. 7 (a) and (b), respectively.
In Fig. 7 (a), it can be observed that the boundary and the direction of the
car are clearly reflected in its $\mathcal{F}_{obj}$. On the other hand, Fig.
7 (b) presents a more complicated scenario, in which both the bike and the
viewpoint move toward to the left, causing the magnitudes and directions of
the flow vectors from $\mathcal{F}_{raw}$ to be unable to provide the correct
clue about the true motion of the bike. This, in turn, may lead to
difficulties and ambiguities when performing control. With flow factorization,
it can be observed from Fig. 7 (b) that $\mathcal{F}_{obj}$ correctly reflects
the direction of the bike (i.e., moving left). This demonstration therefore
validates the applicability of the proposed concept in the real world.

##  VII Conclusions

In this paper, we introduced the use of factorized flow maps as mid-level
representations. To validate the effectiveness and the benefits of combined
usage of factorized flows with the other types of mid-level representations,
we developed a Unity-based framework and four evaluation environments. The
experimental results suggested that factorized flow maps are complementary to
the other mid-level representations, and can enhance the performance of DRL
agents. We also inspected the failure cases, and showed that different mid-
level representations may lead to different failure behaviors of the agents.
We further examined the performance sensitivity of various configurations to
FPS. Finally, we demonstrated the applicability of flow factorization in real
world scenarios.

## References

  * [1] F. Sadeghi and S. Levine, “CAD2RL: real single-image flight without a single real image,” in Robotics: Science and Systems XIII, 2017.
  * [2] L. P. Osco, J. M. Junior, A. P. M. Ramos, et al., “A review on deep learning in UAV remote sensing,” Int. J. Appl. Earth Obs. Geoinformation, vol. 102, p. 102456, 2021.
  * [3] M. Bojarski, D. D. Testa, D. Dworakowski, et al., “End to end learning for self-driving cars,” arXiv preprint arXiv:1604.07316, 2016.
  * [4] A. E. Sallab et al., “Deep reinforcement learning framework for autonomous driving,” arXiv preprint arXiv:1704.02532, 2017.
  * [5] Éloi Zablocki, H. Ben-Younes, P. Pérez, and M. Cord, “Explainability of vision-based autonomous driving systems: Review and challenges,” arXiv preprint arXiv:2101.05307, 2021.
  * [6] S. Levine, C. Finn, et al., “End-to-end training of deep visuomotor policies,” J. Mach. Learn. Res., vol. 17, pp. 39:1–39:40, 2016.
  * [7] S. Levine, P. Pastor, A. Krizhevsky, et al., “Learning hand-eye coordination for robotic grasping with deep learning and large-scale data collection,” Int. J. Robotics Res., vol. 37, pp. 421–436, 2018.
  * [8] D. Kalashnikov, A. Irpan, P. Pastor, et al., “Qt-opt: Scalable deep reinforcement learning for vision-based robotic manipulation,” arXiv preprint arXiv:1806.10293, 2018.
  * [9] A. Singh, L. Yang, C. Finn, and S. Levine, “End-to-end robotic reinforcement learning without reward engineering,” in Robotics: Science and Systems XV, 2019.
  * [10] A. Sax, J. O. Zhang, B. Emi, et al., “Learning to navigate using mid-level visual priors,” in CoRL 2019, 2019.
  * [11] B. Chen et al., “Robust policies via mid-level visual representations: An experimental study in manipulation and navigation,” in CoRL, 2020.
  * [12] Y. Lin, A. Zeng, S. Song, et al., “Learning to see before learning to act: Visual pre-training for manipulation,” in ICRA, 2020.
  * [13] M. Müller, A. Dosovitskiy, B. Ghanem, and V. Koltun, “Driving policy transfer via modularity and abstraction,” in CoRL, 2018.
  * [14] L. Capito, Ü. Özgüner, and K. A. Redmill, “Optical flow based visual potential field for autonomous driving,” in Intelligent Vehicles Symposium, IV 2020, pp. 885–891, IEEE, 2020.
  * [15] B. Zhou, P. Krähenbühl, and V. Koltun, “Does computer vision matter for action?,” Science Robotics, vol. 4, no. 30, 2019.
  * [16] A. Piergiovanni and M. S. Ryoo, “Representation flow for action recognition,” 2019\.
  * [17] Unity technology, “Unity engine.” https://unity.com.
  * [18] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction.  Cambridge, MA, USA: MIT Press, 1st ed., 1998.
  * [19] R. S. Sutton, D. Precup, and S. Singh, “Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning,” Artificial Intelligence, vol. 112, no. 1-2, pp. 181–211, 1999.
  * [20] A. Amiranashvili, A. Dosovitskiy, et al., “Motion perception in reinforcement learning with dynamic objects,” in CoRL, 2018.
  * [21] H.-K. Yang, P.-H. Chiang, M.-F. Hong, and C.-Y. Lee, “Flow-based intrinsic curiosity module,” in IJCAI, 2020.
  * [22] T. Haarnoja, H. Tang, P. Abbeel, and S. Levine, “Reinforcement learning with deep energy-based policies,” in ICML, 2017.
  * [23] T. Haarnoja et al., “Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor,” in ICML, 2018.
  * [24] T. Haarnoja, A. Zhou, K. Hartikainen, et al., “Soft actor-critic algorithms and applications,” arXiv preprint arXiv:1812.05905, 2019.
  * [25] G. Brockman, V. Cheung, L. Pettersson, et al., “Openai gym,” arXiv preprint arXiv:1606.01540, 2016.
  * [26] P. Christodoulou, “Soft actor-critic for discrete action settings,” arXiv preprint arXiv:1910.07207, 2019.
  * [27] O. Delalleau et al., “Discrete and continuous action representation for practical rl in video games,” arXiv preprint arXiv:1912.11077, 2019.
  * [28] Z. Hong, Y. Chen, H. Yang, et al., “Virtual-to-real: Learning to control in visual semantic segmentation,” in IJCAI, 2018.
  * [29] W. Zhao, J. P. Queralta, and T. Westerlund, “Sim-to-real transfer in deep reinforcement learning for robotics: a survey,” in SSCI, 2020.
  * [30] R. N. Elek, A. I. Károly, et al., “Towards optical flow ego-motion compensation for moving object segmentation,” in ROBOVIS, 2020.
  * [31] A. Juliani, V.-P. Berges, E. Teng, et al., “Unity: A general platform for intelligent agents,” arXiv preprint arXiv:1809.02627, 2020.
  * [32] V. Mnih et al., “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, pp. 529–533, 2015.
  * [33] Z. Teed and J. Deng, “RAFT: recurrent all-pairs field transforms for optical flow,” in ECCV, 2020.
  * [34] Stereolabs, “Zed stereo cameras web site.” https://www.stereolabs.com.


# Pixle: a fast and effective black-box attack
based on rearranging pixels

Jary Ponponi  Sapienza University of Rome, Via Eudossiana 18, 00184, Rome,
Italy Corresponding author email<EMAIL_ADDRESS>Simone Scardapane
Sapienza University of Rome, Via Eudossiana 18, 00184, Rome, Italy Aurelio
Uncini  Sapienza University of Rome, Via Eudossiana 18, 00184, Rome, Italy

###### Abstract

Recent research has found that neural networks are vulnerable to several types
of adversarial attacks, where the input samples are modified in such a way
that the model produces a wrong prediction that misclassifies the adversarial
sample. In this paper we focus on black-box adversarial attacks, that can be
performed without knowing the inner structure of the attacked model, nor the
training procedure, and we propose a novel attack that is capable of correctly
attacking a high percentage of samples by rearranging a small number of pixels
within the attacked image. We demonstrate that our attack works on a large
number of datasets and models, that it requires a small number of iterations,
and that the distance between the original sample and the adversarial one is
negligible to the human eye.

##  1 Introduction

Neural Networks (NN) have achieved state-of-the-art performance in image
classification and many other tasks. However, despite their extensive usage,
NNs are highly susceptible to deception performed using adversarial images,
which are samples containing small noise, used to fool the NN and force a
misclassification. Models that operate in a real world scenario can also be
attacked, by physically modifying the objects that have to be classified [1,
2]. This problem is not circumscribed to NNs that operate in the image domain,
but also to ones that work over speech, text, or more general domains.

The majority of the existing methods to generate an adversarial image do it by
constraining the difference between the original image and the adversarial
one, in such a way that the difference between the two is small, and thus
hardly visible to the naked eye. The difference between these images is
usually calculated using a norm $L_{p}$. The value of $p$ influences the
method used by the algorithm, and we can have: $L_{0}$) the difference is
pixel wise, by counting the number of pixels that have been modified by the
method, $L_{1}$) which measures the absolute distance between the images,
$L_{2}$) that measures the distance as Euclidean distance and, $L_{\infty}$)
which is the largest perturbed pixel in the image.

Another important aspect when developing an attack is the number of iterations
required to correctly create an adversarial image. An iteration is an
interrogation of the model: the input is passed though it and the output is
collected. It is a crucial aspect, because many real life models have a limit
on the number of queries that can be performed, and thus it is important to
keep this aspect contained.

Figure 1: Successful adversarial image from ImageNet using the proposed Pixle
attack. The original class of the image is 14 (Passerina Cyanea), while the
misclassified class is 883 (Vase). The $L_{0}$ distance between the original
image and the adversarial one is just $1$ pixel in this case.

Moreover, adversarial methods can be grouped into two categories: white-box
attacks and black-box attacks [3, 4]. In the first case, which is the most
studied one, the methods have full knowledge about the model and its training
procedure. In this case, we can rely on any information within the model
itself, such as gradients for a given sample or the weights of the model
itself. The methods in this category clarify the risks to which the NNs may be
exposed, but usually they do not reflect a real case scenario, in which a
malicious user wants to attack a model, but has a limited number of queries
and no access to the model itself, with the exception of its output. On the
other hand, in the black-box case we can access only the input and the output
of the model, and thus it is closer to a true case scenario.

In this paper we propose a simple yet effective $L_{0}$ norm black-box attack.
Our proposal, called Pixle, is capable of efficiently attacking a model by
measuring only, given an input sample, the confidence of the prediction, as a
probability. Pixle is based on random search, and it creates an effective
adversarial image by rearranging a small set of pixels in the image, showing
also that an image usually contains all the pixels that are necessary to
misclassify it, using a contained number of iterations, as shown in our
experimental results.

##  2 Related Works

The problem of security in machine learning has always been crucial in order
to develop more robust models [5, 6]. The first machine learning model to be
attacked were Support Vector Machines [7], then, in [8] and [9], the authors
discovered that NNs are prone to such attacks as well, which can be easily
accomplished using several gradient based algorithms for obtaining gradient
information of the attacked image, and thus fool the model. After these
discoveries, the security of NNs has become a critical topic for real world
deployments.

Many methods to fool a NN have been proposed in recent years. As said, white-
box attacks are the most studied. As attacks based on $L_{0}$ norm we have
SparseFool [10], which exploits the curvature of decision boundaries, or JSMA
[11], that finds the pixels to attack through saliency maps. Based on others
norms, we have the Fast Gradient Sign Method [9] and its evolution, called
Projected Gradient Descent [12], and Jitter [13], for $L_{\infty}$ norm; both
methods attack the image by changing all the pixels based on their importance,
calculated using the gradient associated to the image. For $L_{1}$ norm we
have attacks that place an upper bound over the absolute sum of the perturbed
values, and the most notable examples are DeepFool [14], EAD [15], and FAB
[16].

Black-box attacks are usually based on $L_{2}$ or $L_{\infty}$ norms. In [17]
the authors proposed a simple policy that produces adversarial images by
perturbing random segments of an image to produce the adversarial counterpart.
In [17], the authors proposed the idea to identify low-frequency perturbations
to improve query efficiency when attacking a model. Another group of methods
is composed by approaches that estimate the gradient of the model without
accessing it directly [18, 19, 20], emulating white-box attacks. Less studied
black-box attacks are the ones based on the $L_{0}$ norm. The first method
developed in this field is called One-Pixel attack [21], that uses a
Differential Evolution (DE) search algorithm [22] to find the best pixels to
replace and the values that must overwrite them. It works well on small
images, but fails when it is not the case; also, it requires thousands of
iterations to find a suitable set of pixels to replace. A similar approach,
but based on larger patches, is called PatchAttack [23], that uses
reinforcement learning to optimally place pre-computed patches over the image
to attack. The drawbacks are that the patches are easily detected, being,
often, very large and visible. Another approach, called ScratchThat [24] is
also based on DE, and literally ‘scratches’ the images by adding lines of
different colors over them to create perturbed images.

As said, studying how to fool NNs is important to understand also how to
protect them from such attacks, and many approaches have been proposed over
the years [25]. One way to achieve this goal is to add adversarial images to
the training data, such that the robustness against adversarial images can be
improved against specific attacks [26, 12]. Others training approaches build
more robust models by distillation [27], ensemble of multiple models or models
that incorporate some degree of uncertainty within them [28]. In addition,
some image processing methods are also proved to be effective in detecting
adversarial images. For instance, in [29] the authors studied how the
detection of adversarial images can be carried out using noise reduction
methods, by comparing the classification after and before applying those
techniques. Similarly, in [29] the authors showed that squeezing colors and
applying spatial smoothing have high success rate on detecting adversarial
images.

##  3 Methodology

Figure 2: Visualization of the mapping procedure used by Pixle. As the image
shows, pixels originating from a small patch of the source image (left) are
mapped into the destination image (right), to build the adversarial sample.
The pixels in the patch are the only ones that are mapped into new positions,
while the others are unchanged. Better viewed in color.

###  3.1 Problem Description

Generating adversarial images that fool a neural network can be formalized as
an optimization problem with constraints.

Let $f:x\in[0,1]\in\mathbb{R}^{(3,w,h)}\rightarrow\mathbb{R}^{c}$ be a
classification function that takes as input a sample of size $(3,w,h)$, were
$3$ are the number of channels while $w$ and $h$ are, respectively, the width
and the height of the image, and produces a vector containing $c$
probabilities (such that $\sum_{i}c_{i}=1$), one associated to each class; a
sample $x$ can be classified as $\arg\max_{i}f_{i}(x)$. In our case, the
function $f$ is a NN.

Given an image $x$, and the associated class $y$, that is classified correctly
by the function $f$, the goal of an attack is to change the prediction of the
function, by producing an adversarial image
$\overline{x}\in\mathbb{R}^{(3,w,h)}$ such that $f(\overline{x})\neq y$. The
image $\overline{x}$ must be similar to $x$, in such a way that the $L_{p}$
norm of the difference is bounded by a constant $\epsilon$:

$\arg\max_{i}f_{i}(\overline{x})\neq y\ \ \ \ \lvert\lvert
x-\overline{x}\rvert\rvert_{p}\leq\epsilon$ (1)

with $\epsilon\in\mathbb{N}_{+}$ in our black-box case. An attack can be
untargeted, as described above, or targeted, by forcing the miss-
classification of the adversarial image to a specific adversarial class
$\overline{y}\neq y$: $f(\overline{x})=\overline{y}$. The task of finding the
perturbed image $\overline{x}$, associated to $x$, can be viewed as a
minimization problem

$\min_{\overline{x}}L(f(\overline{x}),y)\ \ \ \ \lvert\lvert
x-\overline{x}\rvert\rvert_{p}\leq\epsilon\,,$ (2)

for a proper loss function $L$. Here, we use
$L(f(\overline{x}),y)=f_{y}(\overline{x})$ for untargeted attacks and
$L(f(\overline{x}),\overline{y})=1-f_{\overline{y}}(\overline{x})$ for
targeted ones; in the first case we want to minimize the score associated to
the correct class, while in the second one we want to maximize the score
associated to the adversarial target $\overline{y}$.

###  3.2 Pixle

Pixle is a black-box attack based on random search. Despite its simplicity,
random search performs well in many situations and does not depend on gradient
information associated to the objective function $L(\cdot,\cdot)$.

Given an image $x\in\mathbb{R}^{(3,w,h)}$, the main idea of the algorithm is
to sample a random portion $p$ of adjacent pixels from it, that we call patch,
and to rearrange some pixels inside it into other positions, calculated, for
each pixel, using a predefined function $m$, that we call the map function.
Given an image $x$, a generic patch is defined by a $4$-tuple
$p=(w_{p},o_{y},w_{p},h_{p})$, where $0<o_{x}\leq w$ and $0<o_{y}\leq h$ are
the coordinates on the image used as origin point of the patch, while $w_{p}$
and $h_{p}$ are, respectively, the weight and the height of the patch. We
indicate as $P$ the list of index tuples $(i,j)$, that are defined by the
coordinates of the patch, and thus are contained in the rectangle having
vertices as
$[(o_{x},o_{y}),(o_{x}+w_{p},o_{y}),(o_{x},o_{y}+h_{p}),(o_{x}+w_{p},o_{y}+h_{p})]$.
We formalize this list as $P=\left[(o_{x}+i,o_{y}+j)\right]_{\forall
i\in\\{0,\dots,w_{p}\\},j\in\\{0,\dots,h_{p}\\}}$, which has cardinality
$\lvert P\rvert=w_{p}*h_{p}$, assuming that the patch does not exceeds the
boundary of the image, otherwise it is moved in such a way that all the
indexes are inside the image. The mapping function $m$ is defined as:

$m\colon(i,j)\in P\mapsto\mathbb{N}^{2}_{+}\in[1,h]\times[1,w]\,,$ (3)

that returns, for each pixel in the patch, the position where the pixel must
be moved in the original image. Given this function, we can define each pixel
of the adversarial image as:

$\overline{x}_{i,j}=\begin{cases}m(i,j)&(i,j)\in P\\\
x_{i,j}&\text{otherwise}\end{cases}$

The exposed procedure changes only the destination pixels, that are
overwritten by the source ones. This approach is useful if we want to search
for an adversarial image that reduces the distance from the original one. If
we don’t care about this aspect, and we want to speed up the convergence,
another possible approach is to swap the position of the source and
destination pixels at the same time, using the mapping function as before. In
this way, no redundant information is injected into the adversarial image. The
overall procedure, sampling a patch and calculating the mapping function
codomain, remains the same. Fig. 2 visually shows how the pixels are mapped
from the source image to the destination one.

Algorithm 1 Pixle: Restart-Iterative algorithm

input image $x$ with its associated label $y$. Maximum and minimum dimension
for source patch. The number of restarts $R$ and the iterations to perform for
each restart step $T$. The mapping function $m$.

$y=x^{n}$

$\overline{x}\leftarrow x$

$l\leftarrow f_{y}(x)$

for $r=0$ to $R$ do

$x^{r}\leftarrow\overline{x}$

for $t=0$ to $T$ do

Sample $p=(o_{x},o_{y},w_{p},h_{p})$.

Calculate the set $P$

$x^{t}\leftarrow\overline{x}$

for $\forall(i,j)\in P$ do

$(z,k)\leftarrow m(i,j)$

$x^{t}_{z,k}\leftarrow x_{i,j}$

end for

if $f_{y}(x^{t})<l$ then

$l\leftarrow f_{y}(x^{t})$

$x^{r}\leftarrow x^{t}$

end if

end for

$\overline{x}\leftarrow x^{r}$

end forreturn $\overline{x}$

###  3.3 Implementing the mapping function

The function $m$ can be implemented in different ways. Here, since we focus on
the speed of the attack and the number of times that the models is
interrogated, we propose and test the following implementations:

  * •

Random: the function $m$ returns, for each input pixel, a random coordinate
point $(i\sim\mathbb{U}[1,h],j\sim\mathbb{U}[1,w])$, different from the origin
position.

  * •

Similarity: given the image $x$ and the pixel $i$ extracted using an index
tuple from $P$, it returns the position of the most similar pixel in the image
that is not equal to $i$.

  * •

Distance: it works like the Similarity approach, but in this case the position
of the most different pixel is selected, avoiding the ones that have zero
distance.

  * •

Similarity Distribution: like the similarity approach, this is based on the
most similar pixels, but, instead of selecting the position in a deterministic
way, a distribution of positions is calculated using all the distances between
the source pixel and all the others; in this way, the most similar pixels have
a higher probability of being selected. Once the distribution has been
calculated, the mapped position is sampled from it.

  * •

Distance Distribution: it is the distance based version of the Similarity
Distribution exposed above, where most distant pixels are more likely to be
selected.

###  3.4 Search Algorithms

Algorithm 2 Pixle: Iterative algorithm

input image $x$ with its associated label $y$. Maximum and minimum dimension
for source patch. The number of iterations to perform for each restart step
$T$. The mapping function $m$.

$y=x^{n}$

$\overline{x}\leftarrow x$

$l\leftarrow f_{y}(x)$

$x\leftarrow\overline{x}$

for $t=0$ to $T$ do

Sample $p=(o_{x},o_{y},w_{p},h_{p})$.

Calculate the set $P$

$x^{t}\leftarrow\overline{x}$

for $\forall(i,j)\in P$ do

$(z,k)\leftarrow m(i,j)$

$x^{t}_{z,k}\leftarrow x_{i,j}$

end for

if $f_{y}(x^{t})<l$ then

$l\leftarrow f_{y}(x^{t})$

$\overline{x}\leftarrow x^{i}$

end if

end forreturn $\overline{x}$

We propose two different procedures to find the adversarial image. In the
first one, we have two loops, one nested inside the other, and we select only
the attack that leads to the highest decrease of the loss; this attack is
called Restart-Iterative. In the second one, each pixel replacement is used to
create the final adversarial image, and it is called Iterative.

Restart-Iterative: the algorithm is composed of a fixed number of restarts
$R\geq 1$, and within each one a maximum number of iterations $M$ are
performed. Before starting the main loop, the adversarial image is a copy of
the original one, so that all the pixels from the original image are preserved
during the process. At every iteration, we sample a source patch $p$, and
then, using the mapping function $m$, the pixels in the set $P$ are
overwritten. Only the mapping that decreases the loss the most is actually
saved and used in the next restart step. This algorithm is summarized in Alg.
1.

Iterative: in this version, we have only the internal iteration loop, and the
adversarial image is updated each time that an attack decreases the loss
value. The algorithm is summarized in Alg. 2.

Intuitively, the first approach requires more iterations, because only the
best attacks are saved and preserved, while the second approach updates the
adversarial image after each attack. The latter could require less iterations,
but it can happen that an attack leads to a region of the search space which
is sub-optimal, due to the lack of any controlling strategy.

##  4 Experimental evaluation

###  4.1 Experimental setup

The evaluation of the proposed attack is carried out on the following
datasets: CIFAR10 [30], TinyImagenet, and ImageNet [31]. We train CIFAR10 and
TinyImagenet using, respectively, ResNet20 [32] and VGG11 [33] for CIFAR10 and
ResNet50 [32] and VGG16 [33] for TinyImageNet. Regarding ImageNet, we used the
pretrained version of ResNet50 [32] and VGG16 [33], without fine-tuning them.

As training procedure for CIFAR10 and TinyImageNet, we use Stochastic Gradient
Descent, with learning rate set to $0.01$ and momentum to $0.9$. Also, we use
the standard augmentation schema: the images are flipped horizontally with a
probability of $0.5$, and random cropped to the same original size, but after
applying a padding.

For each experiment, we extract the test images to attack from the subset of
test images that are correctly classified by the models. For CIFAR10 we use
$100$ images per each class, while for TinyImageNet and ImageNet, we use,
respectively, $5$ and $1$ images per class. In this way, we test the attacks
on the same number of images for each dataset ($1000$). We also test the
ability of the approaches to perform targeted attacks. For this purpose, we
use $20$ images per class for CIFAR10, resulting in $200$ attacks, excluding
the other datasets.

We compare our proposal to two others black-box attacks based on the $L_{0}$
norm: ScratchThat [24] and OnePixel attack [21]. For the latter, we based our
implementation on the one present in TorchAttacks [34], while the first one is
a custom implementation 111The complete code used to run all the experiments
can be found here. For each attack we performed a search of the best hyper-
parameters, based on the results from the respective papers, in order to
produce the best results in the smallest number of iterations. For
ScratchThat, we use $1$ Bézier Curve for CIFAR10 and $3$ otherwise, with a
population size of $50$ and maximum number of iterations set to $50$ for the
DE algorithm. While for OnePixel, we set the number of pixels to modify equals
to $5$, and, regarding the DE algorithm, we set the population size to $100$
solutions and the number of iterations to $50$. Regarding our approach, we use
the Restart-Iterative approach as random search with at most $100$ restarts
and $50$ iterations per restart cycle. The patches have a size of $3$ pixels,
and the mapping function is the random one, which is calculated again at each
iteration. All the methods are interrupted when the current image is
misclassified by the model, for non targeted attacks, or when the image is
classified as the target class, for targeted ones.

In order to compare the approaches, we use the following metrics:

  * •

Success Rate: it is defined as the percentage of adversarial images that are
misclassified by the neural network.

  * •

Iterations: calculated image wise, it is the number of times that a model is
interrogated while searching the adversarial counterpart of that image.

  * •

$L_{0}$ norm: the number of pixels that the approach has modified.

###  4.2 Main results

Table 1: Results obtained when attacking multiple datasets trained on ResNet
and VGG architectures. For each score, we show the mean and the variance, if
present, calculated over all the images on that dataset. Best results for each
pair dataset-architecture are highlighted in bold.

Dataset | Model | Method | Success rate | Iterations |  $L_{0}$ norm
---|---|---|---|---|---
CIFAR10 |  ResNet18 | OnePixel | $64.7$ | $5125_{\pm 799}$ | $5$
ScratchThat | $99.7$ | $1010$ | $38.3_{\pm 5.2}$
Pixle (Proposed) | $\mathbf{100}$ | $119_{\pm 141}$ | $26.8_{\pm 22.8}$
VGG11 | OnePixel | $84.5$ | $5100$ | $5$
ScratchThat | $99.3$ | $1010$ | $27.64_{\pm 4.8}$
| Pixle (Proposed) | $\mathbf{100}$ | $80_{\pm 145}$ | $20.1_{\pm 21.9}$
TinyImageNet |  ResNet50 | OnePixel | $21.0$ | $5100$ | ${5}$
ScratchThat | $69.7$ | ${1010}$ | $49.1_{\pm 2.2}$
Pixle (Proposed) | $\mathbf{99.6}$ | $310_{\pm 561}$ | $59.0_{\pm 88.5}$
VGG16 | OnePixel | $31.9$ | $5100$ | ${5}$
ScratchThat | $76.6$ | ${1010}$ | $48.6_{\pm 2.4}$
| Pixle (Proposed) | $\mathbf{100}$ | $87_{\pm 201}$ | $21.5_{\pm 30.6}$
ImageNet |  ResNet50 | OnePixel | $47.7$ | $5100$ | $5$
ScratchThat | $82.6$ | $623_{\pm 321}$ | $175.2_{\pm 25.7}$
Pixle (Proposed) | $\mathbf{98.0}$ | $341_{\pm 426}$ | $155.7_{\pm 184.2}$
VGG16 | OnePixel | $31.9$ | $5100$ | $5$
ScratchThat | $81.8$ | $753_{\pm 156}$ | $143.0_{\pm 6.0}$
| Pixle (Proposed) | $\mathbf{99.0}$ | $519_{\pm 780}$ | $98.5_{\pm 137.5}$

####  4.2.1 Non targeted attacks

The results in Table 1 shows that our approach is the most performant one
across the vast majority of scenarios. In fact, it is capable of achieving
almost $100\%$ of success rate on all the datasets, while the others
approaches fail to achieve comparable results when the images become bigger.

Regarding the iterations, we see that our proposal requires a lower number of
iterations even when the dimensions of the images increase with the exception
of OnePixel, which requires fewer iterations than the others, but the success
rate is not sufficiently high to be considered a good attack for big images.
Figure 3 shows how the loss value decreases when attacking CIFAR10 and
ImageNet using our proposal. The images contain the loss value for each
attacked image, as well as the average loss on each iteration (red dots).
According to the images, it can be seen that a set of images are easily
attacked and the associated loss values rapidly decrease, as the bottom images
also show; this happens for both CIFAR10 and ImageNet. In fact, for CIFAR10
our approach correctly attacks $80\%$ of the images after $600$ iterations,
while the same number of images from ImageNet are correctly attacked after
$750$ iterations (approximately).

In the end we analyze the $L_{0}$ norm. The same table shows that our approach
changes less pixels than ScratchThat, when attacking all the dataset. Also, if
we cross reference the results in terms of $L_{0}$ norms and Fig. 3, we see
that a lot of images are correctly attacked using a small number of pixels,
while other images require more iterations (as also shown by the standard
deviation of the metrics). Moreover, the hyperparamenters of our approach can
be adapted in order to achieve a smaller $L_{0}$ loss, at the expense of the
number of iterations or success rate (as shown in Table 2).

####  4.2.2 Targeted attack

Figure 4 shows the results obtained when attacking each class of CIFAR10 with
respect to all the others classes. It shows that OnePixel is incapable of
attacking most of the classes, and presents a low success rate. Regarding
Scratch That, it is capable of perfectly attacking most of the pairs source-
destination, achieving half of the times a perfect score. Our approach,
instead, achieves a perfect score on almost all the attacks, with the
exception of some couples.

####  4.2.3 Dimension of the patches

A crucial aspect of our proposal is the dimension of the patches, and in Table
2 we study this aspect, by calculating all the metrics while varying the
dimensions of them. For each experiment, we use random mapping and at most
$100$ restart, each one composed of $50$ iterations.

We see that, as expected, the bigger the patches are the fewer iterations are
required, but at the same time the distance between the original image and the
adversarial counterpart grows. This happens because more pixels are moved at
the same time, leading rapidly to a minima, which is accepted due to the
callback which interrupts the searching process, that could be reached by
moving fewer pixels as well (this is clearly visible by comparing the results
obtained using $3$ pixels with the one achieved when using $5$ pixels).

Table 2: The results obtained when varying the side dimension of a patch, for
each combination of dataset and architecture, using Pixle.

Dataset | Model | Patch dimension | Success rate | Iterations |  $L_{0}$ norm
---|---|---|---|---|---
CIFAR10 |  ResNet18 | $1$ | $100$ | $314_{\pm 311}$ | $6.9_{\pm 6.1}$
$3$ | $100$ | $119_{\pm 141}$ | $26.8_{\pm 22.8}$
$5$ | $100$ | $78_{\pm 123}$ | $51.6_{\pm 44.8}$
VGG11 | $1$ | $99.1$ | $343_{\pm 726}$ | $7.3_{\pm 13.6}$
$3$ | $100$ | $80_{\pm 145}$ | $20.1_{\pm 21.9}$
| $5$ | $100$ | $56_{\pm 236}$ | $38.2_{\pm 33.9}$
TinyImageNet |  ResNet50 | $1$ | $96.81$ | $754_{\pm 1055}$ | $15.3_{\pm 20.0}$
$3$ | $99.6$ | $310_{\pm 561}$ | $59.0_{\pm 88.5}$
$5$ | $99.8$ | $182_{\pm 379}$ | $98.0_{\pm 137.7}$
VGG16 | $1$ | $99.6$ | $242_{\pm 172}$ | $18.0_{\pm 29.9}$
$3$ | $100$ | $87_{\pm 201}$ | $21.5_{\pm 30.6}$
| $5$ | $100$ | $52_{\pm 120}$ | $43.2_{\pm 49.6}$
ImageNet |  ResNet50 | $1$ | $94.5$ | $1417_{\pm 1376}$ | $28.9_{\pm 27.3}$
$3$ | $98.0$ | $341_{\pm 426}$ | $155.7_{\pm 184.2}$
$5$ | $99.5$ | $223.3_{\pm 315}$ | $286.2_{\pm 372.3}$
VGG16 | $1$ | $95.6$ | $1194_{\pm 1319}$ | $24.4_{\pm 26.1}$
$3$ | $99.0$ | $519_{\pm 780}$ | $98.5_{\pm 137.5}$
| $5$ | $99.5$ | $339_{\pm 609}$ | $183.9_{\pm 291.7}$

(a) CIFAR10 results using VGG11.

(b) ImageNet results using ResNet50.

Figure 3: Each figure shows, on top, how the losses (the probability
associated to the correct class) change during the iterations of our proposal,
using the Restart-Iterative algorithm (the red dots are the average loss
calculated on that iteration); while the bottom image shows how many images
are left to attack after each iteration. Better viewed in colors.

(a) The results obtained using OnePixel attack.

(b) The results obtained using Scratch That attack

(c) The results obtained using our proposal.

Figure 4: The images show the success rate on ResNet18 trained using CIFAR10.
The results are calculated using $20$ test images, classified correctly by the
model, for each class. Each matrix contains the percentage of attacks that
have been successfully completed.

###  4.3 Ablation studies

We perform an ablation study to show how the individual design decisions
improve the performance of Pixle, both in terms of scores and convergence.

####  4.3.1 Restart-Iterative vs Iterative

Table 3: The results obtained using VGG11 trained on CIFAR10. For the
Iterative-Restart approach we fixed the number of iterations to $59$.

| Restart-Iterative (restarts) | Iterative (iterations)
---|---|---
| 50 | 100 | 250 | 500 | 50 | 100 | 250 | 500 | 1000 | 2000 | 10000
Success Rate | $95.5$ | $98.2$ | $99.7$ | $100.0$ | $6.1$ | $77.7$ | $87.9$ | $90.5$ | $92.4$ | $93.1$ | $94.3$
Iterations | $170_{\pm{243}}$ | $199_{\pm 362}$ | $222_{\pm 531}$ | $209_{\pm 468}$ | $31_{\pm 17}$ | $45_{\pm 36}$ | $69_{\pm 79}$ | $95_{\pm 147}$ | $131_{\pm 264}$ | $206_{\pm 511}$ | $697_{\pm 2365}$
$L_{0}$ norm | $8.9_{\pm 11.6}$ | $10.2_{\pm 16.9}$ | $10.9_{\pm 22.5}$ | $10.9_{\pm 20.3}$ | $12.2_{\pm 9.1}$ | $16.1_{\pm 13.7}$ | $18.7_{\pm 18.9}$ | $20.4_{\pm 23.0}$ | $20.4_{\pm 23.4}$ | $21.1_{\pm 25.5}$ | $21.86_{\pm 28.2}$

In this section we explore how the choice of the search algorithm affects the
results. Table 4.3 shows the results obtained training VGG11 on CIFAR10, while
changing the number of iterations. To this end, the algorithm attacks $1$
pixel at a time, using a random mapping calculated at each iteration. We can
see that the random search based on the restarts is more effective with
respect to all the metrics. In fact, when setting the limit to $100$
iterations and $50$ restarts, we achieve better results then the iterative
algorithm with a limit of $10000$ iterations.

####  4.3.2 Mapping function

Table 4: The results obtained when varying the mapping function. The attacked
model is VGG11 trained on CIFAR10.

Mapping function | Success rate | Iterations |  $L_{0}$ norm
---|---|---|---
Distance | $17.6$ | $8297_{\pm 3697}$ | $40.1_{\pm 17.9}$
Similarity | $96.5$ | $1029_{\pm 2196}$ | $10.0_{\pm 18.7}$
Distance distribution | $99.3$ | $536_{\pm 1260}$ | $5.9_{\pm 11.9}$
Similarity distribution | $99.1$ | $605_{\pm 1425}$ | $3.1_{\pm 7.3}$

In this section we study how the selection of mapping function affects the
final scores, shown in Table 4. We see that, when operating with a
deterministic mapping, the number of required iterations, as well as the
$L_{0}$ norm, are higher than the distribution counterparts. This happens
because the randomness of the distributions force the approach to explore the
space, avoiding local minima.

##  5 Conclusion

In this paper we proposed a novel black-box attack called Pixle. Our attack,
despite using only the probability of the prediction returned by the attacked
model, proved to be effective over a wide range of datasets and architectures
types, and on multiple metrics, such as the number of iterations required and
the number of modified pixels.

As future work, we aim to understand the correlation between the attacked
class and the pixels in the image, especially when performing a targeted
attack. Furthermore, we would like to expand the proposed approach also on
other domains, such as text and audio. In the end, we would like to understand
if the proposed attack can be further studied, in order to create a defense
algorithm against $L_{0}$ attacks.

## References

  * [1] A. Athalye, L. Engstrom, A. Ilyas, K. Kwok, Synthesizing robust adversarial examples, in: International conference on machine learning, PMLR, 2018, pp. 284–293.
  * [2] K. Eykholt, I. Evtimov, E. Fernandes, B. Li, A. Rahmati, C. Xiao, A. Prakash, T. Kohno, D. Song, Robust physical-world attacks on deep learning visual classification, in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 1625–1634.
  * [3] S. Bhambri, S. Muku, A. Tulasi, A. B. Buduru, A survey of black-box adversarial attacks on computer vision models, arXiv preprint arXiv:1912.01667 (2019).
  * [4] S. Qiu, Q. Liu, S. Zhou, C. Wu, Review of artificial intelligence adversarial attack and defense technologies, Applied Sciences 9 (5) (2019).
  * [5] M. Barreno, B. Nelson, A. D. Joseph, J. D. Tygar, The security of machine learning, Machine Learning 81 (2) (2010) 121–148.
  * [6] M. Barreno, B. Nelson, R. Sears, A. D. Joseph, J. D. Tygar, Can machine learning be secure?, in: Proceedings of the 2006 ACM Symposium on Information, computer and communications security, 2006, pp. 16–25.
  * [7] B. Biggio, B. Nelson, P. Laskov, Poisoning attacks against support vector machines, arXiv preprint arXiv:1206.6389 (2012).
  * [8] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, R. Fergus, Intriguing properties of neural networks, in: 2nd International Conference on Learning Representations, ICLR 2014, 2014.
  * [9] I. Goodfellow, J. Shlens, C. Szegedy, Explaining and harnessing adversarial examples, in: International Conference on Learning Representations, 2015, pp. 1–11.
  * [10] A. Modas, S.-M. Moosavi-Dezfooli, P. Frossard, Sparsefool: a few pixels make a big difference, in: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2019, pp. 9087–9096.
  * [11] N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, A. Swami, The limitations of deep learning in adversarial settings, in: 2016 IEEE European symposium on security and privacy (EuroS&P), IEEE, 2016, pp. 372–387.
  * [12] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, A. Vladu, Towards deep learning models resistant to adversarial attacks, in: International Conference on Learning Representations, 2018.
  * [13] L. Schwinn, R. Raab, A. Nguyen, D. Zanca, B. Eskofier, Exploring robust misclassifications of neural networks to enhance adversarial attacks, arXiv e-prints (2021) arXiv–2105.
  * [14] S.-M. Moosavi-Dezfooli, A. Fawzi, P. Frossard, Deepfool: a simple and accurate method to fool deep neural networks, in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 2574–2582.
  * [15] Y. Sharma, P.-Y. Chen, Attacking the madry defense model with $l\\_1$-based adversarial examples, arXiv preprint arXiv:1710.10733 (2017).
  * [16] F. Croce, M. Hein, Minimally distorted adversarial examples with a fast adaptive boundary attack, in: International Conference on Machine Learning, PMLR, 2020, pp. 2196–2205.
  * [17] N. Narodytska, S. Kasiviswanathan, Simple black-box adversarial attacks on deep neural networks, in: 2017 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2017, pp. 1310–1318.
  * [18] A. Ilyas, L. Engstrom, A. Athalye, J. Lin, Black-box adversarial attacks with limited queries and information, in: International Conference on Machine Learning, PMLR, 2018, pp. 2137–2146.
  * [19] M. Alzantot, Y. Sharma, S. Chakraborty, H. Zhang, C.-J. Hsieh, M. B. Srivastava, Genattack: Practical black-box attacks with gradient-free optimization, in: Proceedings of the Genetic and Evolutionary Computation Conference, 2019, pp. 1111–1119.
  * [20] A. N. Bhagoji, W. He, B. Li, D. Song, Exploring the space of black-box attacks on deep neural networks, arXiv preprint arXiv:1712.09491 (2017).
  * [21] J. Su, D. V. Vargas, K. Sakurai, One pixel attack for fooling deep neural networks, IEEE Transactions on Evolutionary Computation 23 (5) (2019) 828–841.
  * [22] R. Storn, K. Price, Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces, Journal of global optimization 11 (4) (1997) 341–359.
  * [23] C. Yang, A. Kortylewski, C. Xie, Y. Cao, A. Yuille, Patchattack: A black-box texture-based attack with reinforcement learning, in: European Conference on Computer Vision, Springer, 2020, pp. 681–698.
  * [24] M. Jere, L. Rossi, B. Hitaj, G. Ciocarlie, G. Boracchi, F. Koushanfar, Scratch that! an evolution-based adversarial attack against neural networks, arXiv preprint arXiv:1912.02316 (2019).
  * [25] X. Yuan, P. He, Q. Zhu, X. Li, Adversarial examples: Attacks and defenses for deep learning, IEEE transactions on neural networks and learning systems 30 (9) (2019) 2805–2824.
  * [26] R. Huang, B. Xu, D. Schuurmans, C. Szepesvári, Learning with a strong adversary, arXiv preprint arXiv:1511.03034 (2015).
  * [27] N. Papernot, P. McDaniel, X. Wu, S. Jha, A. Swami, Distillation as a defense to adversarial perturbations against deep neural networks, in: 2016 IEEE symposium on security and privacy (SP), IEEE, 2016, pp. 582–597.
  * [28] J. Gawlikowski, C. R. N. Tassi, M. Ali, J. Lee, M. Humt, J. Feng, A. Kruspe, R. Triebel, P. Jung, R. Roscher, et al., A survey of uncertainty in deep neural networks, arXiv preprint arXiv:2107.03342 (2021).
  * [29] B. Liang, H. Li, M. Su, X. Li, W. Shi, X. Wang, Detecting adversarial image examples in deep neural networks with adaptive noise reduction, IEEE Transactions on Dependable and Secure Computing (2018).
  * [30] A. Krizhevsky, G. Hinton, et al., Learning Multiple Layers of Features from Tiny Images (2009).
  * [31] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, L. Fei-Fei, Imagenet: A large-scale hierarchical image database, in: 2009 IEEE Conference on Computer Vision and Pattern Recognition, 2009, pp. 248–255.
  * [32] K. He, X. Zhang, S. Ren, J. Sun, Deep Residual Learning for Image Recognition, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016, pp. 770–778.
  * [33] K. Simonyan, A. Zisserman, Very Deep Convolutional Networks for Large-Scale Image Recognition, arXiv preprint arXiv:1409.1556 (2014).
  * [34] H. Kim, Torchattacks: A pytorch repository for adversarial attacks, arXiv preprint arXiv:2010.01950 (2020).