# The Pyro game: a slow intelligent fire

M. E. Messinger, S. Yarnell Partially supported by NSERC Discovery
GrantSupported by a Mount Allison Independent Student Research Award.

###### Abstract

In the Firefighter problem, a fire breaks out at a vertex of a graph and at
each subsequent time step, the firefighter chooses a vertex to protect and
then the fire spreads from _each_ burned vertex to every unprotected
neighbour. The problem can be thought of as a simplified model for the spread
of gossip or disease in a network. We introduce a new two-player variation
called the Pyro game, in which at each step, the fire spreads from _one_
burned vertex to all unprotected neighbours of that vertex. The fire is no
longer automated and aims to maximize the number of burned vertices. We show,
that unlike the Firefighter problem, one firefighter can contain a fire on the
Cartesian grid in the Pyro game. We also study both the Pyro Game and the
Firefighter Problem on the infinite strong grid and the complexity of the Pyro
game.

##  1 Introduction to the Pyro game

The Firefighter problem, introduced in 1995 by Harnell [10] is a deterministic
model of the spread of fire, gossip, or disease in a network. Initially, a
fire breaks out at a vertex in a graph, and this vertex is said to be
_burned_. At each subsequent step, the firefighter chooses a vertex to
_protect_ and then the fire acts without intelligence and spreads from each
burned vertex to all unprotected neighbouring vertices. Once a vertex is
protected or burned, it remains in that state forever. In a finite graph, the
process terminates when the fire can no longer spread; at this time, any
vertex (including protected vertices) that has not been burned is _saved_ and
naturally, the goal for the firefighter is often to maximize the number of
saved vertices. On an infinite graph, we may either consider the surviving
rate, which is the proportion of the vertices that saved when one firefighter
protects one vertex at each step; or determine the minimum $k$ such that if
$k$ vertices are protected at each time step, the process will terminate (i.e.
such that there is some finite step after which no vertex will be burned). See
the survey [13] or more recent advances in [2, 6, 7, 9] for example.

We introduce a variation of the Firefighter problem where during each step,
the fire chooses _one_ burned vertex and spreads from that vertex to all its
unprotected neighbours. Though the fire is “slowed”, it is no longer automated
and can act with intelligence. Formally, the _Pyro game_ is a two-player game,
played on a connected graph. At step $0$, the pyro player chooses a vertex and
burns it. At each subsequent time step, the firefighter player (which can be
thought of as a set of $k\in\mathbb{N}$ firefighters) protects $k$ unburned
vertices and then the pyro player chooses one burned vertex and burns _from_
that vertex to its unprotected, unburned neighbours of the vertex. Once a
vertex is burned or protected, it will remain in that state for the duration
of the game. If the graph is finite, there will a finite step after which no
vertex can be burned. If the graph is infinite, this may or may not be the
case. As a result, we say a fire on an infinite graph can be contained if the
firefighter player plays optimally, there is some finite step after which no
unprotected unburned vertex will be burned. On a finite graph, the pyro
player’s goal is to burn as many vertices as possible, while the firefighter
player’s goal is to maximize the number of vertices saved (i.e. minimize the
number of burned vertices). On an infinite graph, the firefighter player’s
goal is to contain the fire whereas the pyro player’s goal is to avoid being
contained. Henceforth, we will simply refer to the pyro player and the
firefighter player as the pyro and the firefighter(s), respectively.

In terms of the maximum number of vertices that can be saved, the Pyro game
and the Firefighter problem yield the same result for some graphs and very
different results for others. For example, in both problems the maximum number
of vertices that can be saved on a path $P_{n}=\\{v_{1},v_{2},\dots,v_{n}\\}$
is $n-2$ if the initial burned vertex is a non-leaf and $n-1$ if the initial
burned vertex is a leaf. To do this, at each step, the firefighter simply
protects a vertex adjacent to a burned vertex. On the other hand, the maximum
number of vertices that can be saved in the Pyro game can also be very
different than in the Firefighter problem. Suppose that vertex $r$ of the
graph shown in Figure 1 (a) is burned at time $t=0$. Within the dotted lines,
a clique on $7$ vertices has been drawn, but we imagine a clique on $m$
vertices (for some large integer $m$). One can observe that the optimal move
for the firefighter, in both the Firefighter problem and the Pyro game, is to
protect a neighbour of $r$, say $v_{1}$, during step $t=1$. An example of the
Firefighter problem is shown in Figure 1 (b) and an example of the Pyro game
is shown in Figure 1 (c); the white circled vertices indicate protected
vertices while the large black circles (and the large black square) indicate
burned vertices.

Figure 1: An example where the maximum number of vertices saved for the Pyro
game greatly exceeds that of the Firefighter problem.

In the Firefighter problem, the fire spreads to all unprotected neighbours of
$r$ at the end of step $t=1$. Suppose the firefighter protects vertex $v_{2}$
as shown in Figure 1 (b). At the end of step $t=2$ the fire spreads to
vertices $v_{3}$ and $v_{4}$. At the beginning of step $t=3$, the firefighter
can protect $v_{5}$, then the fire spreads to $v_{6}$. Finally, the
firefighter protects $x$, then the fire spreads to all unprotected vertices in
$K_{m}$; this results in only $5$ of $m+9$ vertices being saved (see Figure 1
(b)).

In the Pyro game, the pyro burns from $r$ to all unprotected neighbours at the
end of step $t=1$. Suppose the firefighter then protects vertex $v_{2}$. At
the end of step $t=2$, the pyro spreads to either $v_{3}$ or $v_{4}$, suppose
to $v_{3}$. At the beginning of step $t=3$, the firefighter protects $v_{5}$,
then the pyro spreads to $v_{4}$. Finally, the firefighter protects $v_{6}$
and the pyro can no longer spread; this results in $m+3$ of $m+9$ vertices
being saved. (see Figure 1 (c)).

The Pyro game is also closely related to Conway’s famous Angel Game [4] and
Epstein’s game of Quadraphage (Square-Eater) [8]. The latter is played on a
generalized $m\times n$ chessboard with two players. The Chess player has a
single chess piece, the King which starts at the center square of the board
(or as close as possible if $mn$ is even). The Chess player’s object is to
move the King piece to any square on the edge of the board while the object of
the square-eater player is to prevent this from occurring. The players
alternate turns. On the Chess player’s turn, the King is moved to any non-
eaten neighbouring square. On the square-eater player’s turn, any $q$ squares
are eaten. The game of Quadraphage with $q=1$ is equivalent to the well-known
Angel Game with an angel of power 1. With optimal play, the square-eater
player wins the game of Quadraphage with $q=1$ on a board as small as
$33\times 33$; the proof was shown in [1] and nicely explained in [12]. The
Pyro game differs however, as the pyro can choose any burned vertex from which
to burn (not simply the last vertex burned) and when the pyro burns from a
vertex $x$, it does not simply spread to one neighbour of $x$, but to all
unprotected unburned neighbours of $x$.

In Section 2, we determine the complexity of the Pyro game in terms of the
maximum number of vertices that can be saved and show the decision problem is
$\mathcal{NP}$-hard for bipartite graphs. We then consider the Pyro game on
the infinite Cartesian and strong grids. In the Firefighter problem, one
firefighter cannot contain a fire on the infinite Cartesian grid, but an
average of slightly more than $\frac{3}{2}$ firefighters can. In Section 3, we
show that in the Pyro game, one firefighter can contain a fire on the infinite
Cartesian grid. In Section 4, we consider the Pyro game on the infinite strong
grid; we provide an algorithm for two firefighters to contain the fire. For
completeness, we also consider the Firefighter problem on the strong grid: we
prove three firefighters cannot contain a fire on the infinite strong grid and
provide an algorithm for four firefighters to contain the fire.

##  2 Complexity of the Pyro game

Let $MSV_{p}(G,r)$ denote the maximum number of vertices of graph $G$ that can
be saved if the pyro initially burns vertex $r$ and both players move
optimally in the pyro game. By “optimally”, we mean that the firefighter will
aim to maximize the number of saved vertices and the pyro will aim to maximize
the number of burned vertices (or equivalently, minimize the number of saved
vertices). Consider the following decision problem:

PYRO

_Instance:_ A rooted graph $(G,r)$ and an integer $k\geq 1$.

_Question:_ Is $MVS_{p}(G,r)\geq k$?

Theorem 1 establishes the problem is $\mathcal{NP}$-hard for bipartite graphs,
which implies the result for general graphs. The transformation is from EXACT
COVER BY 3-SETS and the proof is similar to the proof of FIREFIGHTER in [14]
though the graph construction differs.

EXACT COVER BY 3-SETS (X3C)

_Instance:_ A set $X$ with $|X|=3q$ and a collection $\mathcal{C}$ of
$3$-element subsets of $X$.

_Question:_ Does $\mathcal{C}$ contain an exact cover for $X$?

######  Theorem 1.

PYRO is $\mathcal{NP}$-hard for bipartite graphs.

###### Proof.

Let $\mathcal{C}=\\{C_{1},C_{2},\dots,C_{|\mathcal{C}|}\\}$. We construct a
rooted bipartite graph $(G,r)$ and a positive integer $k$ such that at least
$k$ vertices of $(G,r)$ can be saved if and only if there is an exact cover of
$\mathcal{C}$.

Begin with a root vertex $r$, and $|\mathcal{C}|$ vertices
$c_{1},c_{2},\dots,c_{|\mathcal{C}|}$ (that represent the elements
$C_{1},C_{2},\dots,C_{|\mathcal{C}|}$ of $\mathcal{C}$) each joined to $r$ by
a path of length $q$. For $i=1,2,\dots,q-1$, we add in edges so that every
vertex distance $i$ from $r$ is adjacent to all vertices distance $i+1$ from
$r$. Finally, for each $i,j\in\\{1,\dots,|\mathcal{C}|\\}$ with $i\neq j$, if
$C_{i}\cap C_{j}=\emptyset$ then we join the corresponding vertices $c_{i}$
and $c_{j}$ by $9q^{4}$ paths of length $2$. Let $P$ be the set of vertices
added in this last step of the graph construction.

Without loss of generality, let
$\mathcal{C}^{\prime}=\\{C_{1},C_{2},\dots,C_{|\mathcal{C}^{\prime}|}\\}$ be a
subcollection of mutually disjoint $3$-sets of $X$ that is of maximum
cardinality.

Suppose that $X$ contains an exact cover by $\mathcal{C}$. Then every element
of $X$ occurs in exactly one member of $\mathcal{C}^{\prime}$ and
$|\mathcal{C}^{\prime}|=q$. Without loss of generality, vertices
$c_{1},c_{2},\dots,c_{q}$ represent the elements of $\mathcal{C}^{\prime}$.
Since $C_{1},C_{2},\dots,C_{q}$ represent mutually disjoint sets, each pair of
distinct vertices $c_{i}$, $c_{j}$ with $i,j\in\\{1,\dots,q\\}$ has $9q^{4}$
paths of length $2$ between them. In total, there are $\binom{q}{2}(9q^{4})$
paths of length $2$. For $i\in\\{1,2,\dots,q\\}$, at step $i$, the firefighter
protects vertex $c_{i}$. There are at least $k=q+\binom{q}{2}(9q^{4})$
vertices saved.

Suppose the number of vertices that can be saved is at least $k=q+{q\choose
2}(9q^{4})$. After $q$ steps, suppose $\ell<q$ vertices of
$c_{1},c_{2},\dots,c_{|\mathcal{C}|}$ have been protected. Then after $q$
steps, at most ${q-1\choose 2}(9q^{4})+(q-\ell)$ vertices in $P$ are
protected. So after $q$ steps, the maximum number of vertices that can be
saved is $q+\tbinom{q-1}{2}9q^{4}<k$. As this yields a contradiction, we
conclude exactly $q$ vertices of $c_{1},c_{2},\dots,c_{|\mathcal{C}|}$ are
protected after $q$ steps. Next, suppose that these $q$ vertices do not
correspond to a collection of pairwise disjoint $3$-sets. Then the maximum
number of vertices saved is $q+\tbinom{q}{2}9q^{4}-9q^{4}<k$. Therefore, the
$q$ protected vertices must correspond to a collection of pairwise disjoint
$3$-sets and $|\mathcal{C}^{\prime}|=q$.∎

##  3 The infinite Cartesian grid

In the Firefighter problem, one firefighter cannot contain a fire on the
infinite Cartesian grid [17]. It was shown in [15] that if an average of
$\tfrac{3}{2}+\tfrac{1}{3x+2}$ vertices are protected at each step (protecting
at most $2$ vertices at each step), the fire can be contained by time step
$12x+7$ for $x\in\mathbb{N}$. A similar result was independently proven in
[16]; they additionally proved that any ratio greater than $\frac{3}{2}$ can
be achieved. In both [15] and [16], the authors also conjectured that if
firefighters protect an average of exactly $\tfrac{3}{2}$ vertices at each
step, a fire on an infinite Cartesian grid cannot be contained; this was later
proven by [5]. By contrast, we next show that in the Pyro game, one
firefighter can contain a fire on the Cartesian grid.

To do this, we provide a simple algorithm to describe the vertices protected
at each step $t>0$ that leave the pyro unable to burn a vertex distance $48$
from the vertex $(0,0)$ burned at $t=0$. The simplicity of the algorithm
results from giving the pyro extra “power” for the first $44$ steps and by
reducing the firefighter’s “power” at every step. Specifically, for the first
$44$ steps, we allow the pyro to burn from each burned vertex to every
neighbouring vertex. We additionally impose restrictions on the firefighter
and permit the firefighter to only protect vertices that are exactly distance
$48$ from the original burned vertex for all $t\geq 1$. The algorithm for
protecting vertices, presented below, will prevent the pyro from ever burning
a vertex distance $48$ from the original burned vertex.

Let $D_{48}$ be the set of vertices distance $48$ from $(0,0)$ on the infinite
Cartesian grid and let $T$ be the set of vertices $(x,y)\in D_{48}$ where

$(-5\leq x\leq 5)\wedge\Big{(}(43\leq y\leq 48)\vee(-48\leq
y\leq-43)\Big{)}\text{~{}or}$ $(-5\leq y\leq 5)\wedge\Big{(}(43\leq x\leq
48)\vee(-48\leq x\leq-43)\Big{)}$

as partially illustrated in Figure 2 by the shaded area.

Figure 2: A subset of vertices of $T$ on the Cartesian grid.

If vertex $(x,y)$ is distance $d>0$ to the nearest vertex in $D_{48}$, then
the threat set of $(x,y)$, denoted $Th((x,y))$ is defined to be the set of
vertices in $D_{48}$ that are distance $d$ from $(x,y)$. That is,

$Th((x,y))=\\{(u,v)\in D_{48}~{}|~{}d((x,y),(u,v))=d\\}.$

We define the center of a threat set $Th((x,y))$ to be the vertex (or
vertices) in $Th((x,y))$ with the median $x$-coordinate(s). For example, if
$(x^{\prime},y^{\prime})\in D_{44}$ with $x^{\prime}\geq 1$ and
$y^{\prime}\geq 1$ then

$Th((x^{\prime},y^{\prime}))=\\{(x^{\prime},y^{\prime}+4),(x^{\prime}+1,y^{\prime}+3),(x^{\prime}+2,y^{\prime}+2),(x^{\prime}+3,y^{\prime}+1),(x^{\prime}+4,y^{\prime})\\}$

with center vertex $(x^{\prime}+2,y^{\prime}+2)$. If
$(x^{\prime},y^{\prime})\in D_{45}$ with $x^{\prime}\geq 1$ and
$y^{\prime}\geq 1$ then

$Th((x^{\prime},y^{\prime}))=\\{(x^{\prime},y^{\prime}+3),(x^{\prime}+1,y^{\prime}+2),(x^{\prime}+2,y^{\prime}+1),(x^{\prime}+3,y^{\prime})\\}$

with center vertices $(x^{\prime}+1,y^{\prime}+2)$ and
$(x^{\prime}+2,y^{\prime}+1)$.

######  Algorithm 2.

The Pyro game with one firefighter on an infinite Cartesian grid.

1) At step $0$, the pyro chooses a vertex to burn; label this vertex $(0,0)$.

2) For $1\leq t\leq 44$, at step $t$, the firefighter protects an unprotected
vertex of $T$ and then the pyro burns from every vertex distance $t-1$ from
the origin, to every vertex distance $t$ from the origin.

3) At the beginning of step $45$, the firefighter protects the last
unprotected vertex of $T$.

4) For $t\geq 45$, during step $t$, the pyro will choose one burning vertex
$(x,y)$ and spread from $(x,y)$ to all unprotected unburned neighbours:

  1. a)

if the pyro burns from a vertex in $D_{44}\cup D_{45}\cup D_{46}$ during step
$t$, then during step $t+1$, the firefighter will protect an unprotected
vertex of $Th((x,y))$, closest to the center, arbitrarily breaking ties. If
all vertices in $Th((x,y))$ were protected prior to step $t+1$, the
firefighter protects an arbitrary vertex in $D_{48}$.

  2. b)

if the pyro burns from a vertex $(x,y)\in D_{47}$ during step $t$, then if
$\exists(u,v)\in N((x,y))\backslash D_{48}$ that was unburned prior to step
$t$, protect a vertex in $Th((u,v))$ closest to the center, arbitrarily
breaking ties. If no such $(u,v)$ exists or every vertex in $Th((u,v))$ was
protected prior to step $t+1$, protect an arbitrary vertex in $D_{48}$.

######  Theorem 3.

Using Algorithm 2, one firefighter can prevent the pyro from burning any
vertex distance $48$ from the original burned vertex $(0,0)$ on the infinite
Cartesian grid.

###### Proof.

For a contradiction, suppose the pyro burns from a vertex in $D_{47}$ during
step $t+1$ to spread to a vertex of $D_{48}$. We further assume that step
$t+1$ is the least step by which a vertex of $D_{48}$ can be burned. Then the
pyro must have burned from a vertex $(x,y)\in D_{46}$ during step $t$. By 4)
a), the firefighter protects one vertex from the set $Th((x,y))$ during step
$t+1$ (or an arbitrary vertex of $D_{48}$ if the vertices in $Th((x,y))$ were
all previously protected). Using Algorithm 2, we next show that by the end of
step $t+1$, all vertices in the set $Th((x,y))$ will be protected which proves
that if the pyro burns from a vertex in $N((x,y))\cap D_{47}$ during step
$t+1$, no vertex of $D_{48}$ will be burned during step $t+1$.

By 2) and 3), after the firefighter has protected a vertex during step $45$,
every vertex of $T$ will have been protected. Observe that for $(x,y)\in
D_{46}$ where $-3\leq x\leq 3$ or $-3\leq y\leq 3$, by 2) and 3), every vertex
in the set $Th((x,y))$ protected by the end of step $45<t+1$. If $(x,y)\in
D_{46}$ where $x=\pm 4$ or $y=\pm 4$, then by 2) and 3), two of the three
vertices of $Th((x,y))$ are protected by the end of step $45<t+1$ and by 4)
a), all vertices in $Th((x,y))$ are protected by the end of step $t+1$. Thus,
we may assume $x\notin\\{-4,-3,-2,-1,0,1,2,3,4\\}$ and
$y\notin\\{-4,-3,-2,-1,0,1,2,3,4\\}$ for the remainder of the proof. This
implies $|Th((x,y))|=3$.

Without loss of generality, suppose $x\geq 5$ and $y\geq 5$ and consider the
vertex in $N((x,y))=\\{(x-1,y),(x,y+1),(x+1,y),(x,y-1)\\}$ that the pyro
burned from most recently prior to step $t$. If the pyro burned from $(x,y+1)$
(or $(x+1,y)$) during some step $t^{*}<t$ then by the end of step $t^{*}+1$,
vertices $(x,y+2)$ and $(x+1,y+1)$ (or $(x+1,y+1)$ and $(x+2,y)$) were
protected; otherwise the pyro could have burned a vertex of $D_{48}$ during
step $t^{*}+1<t+1$ which contradicts our assumption that the earliest step by
the pyro can burn a vertex of $D_{48}$ is step $t+1$.

Suppose the pyro burned from $(x-1,y)$ during some step $t^{*}<t$. Note
$Th((x-1,y))=\\{(x,y+3),(x+1,y+2),(x+2,y+1),(x+3,y)\\}$. If both center
vertices $(x+1,y+2),(x+2,y+1)$ were protected prior to step $t^{*}+1$, then
the firefighter protects $(x,y+3)$ or $(x+3,y)$ during step $t^{*}+1$. If the
firefighter protects $(x,y+3)$ during step $t^{*}+1$, then the firefighter
protects $(x+3,y)$ during step $t+1$ and so that all vertices of $Th((x,y))$
are protected before the pyro burns during step $t+1$.

Thus, we assume at most one of $(x+1,y+2),(x+2,y+1)$ was protected prior to
step $t^{*}+1$. If the pyro burned from $(x-1,y+1)$ during step
$t^{**}<t^{*}$, then the vertices in $Th((x-1,y+1))$ are all protected by the
end of step $t^{**}+1$, otherwise the pyro could have burned a vertex of
$D_{48}$ prior to step $t+1$. By 4) a), the vertices of
$Th((x,y))=Th((x-1,y+1))\cup\\{(x,y+2)\\}$ are protected by the end of step
$t+1$.

If the pyro burned from $(x-2,y)$ during step $t^{**}<t^{*}$, the by 4) a), as
$(x,y+2)$ is the center of $Th((x-2,y))$, it is protected by the end of step
$t^{**}+1$. As a result, by 4) a), $(x+1,y+1)\in Th((x-1,y))$ is protected by
the end of step $t^{*}+1$ and consequently, $(x+2,y)\in Th((x,y))$ is
protected by the end of step $t+1$. Observe then, that the vertices of
$Th((x,y))=\\{(x,y+2),(x+1,y+1),(x+2,y)\\}$ are all therefore protected by the
end of step $t+1$. A very similar argument shows that if the pyro burned from
$(x-1,y-1)$ during step $t^{**}<t^{*}$ then the vertices of $Th((x,y))$ are
all protected by the end of step $t+1$.

The argument to show that if the pyro burned from $(x,y-1)$ instead of
$x-1,y)$ during some step $t^{*}<t$ then all vertices of $Th((x,y))$ are
protected by the end of step $t+1$ is extremely similar to the previous case
and has therefore been omitted.∎

Though we proved that one firefighter can prevent the pyro from burning a
vertex distance $48$ from the original burned vertex, this is far from optimal
and we conjecture a much stronger result.111The authors claim to have a proof
of the conjecture, but as it is an extremely long and tedious proof, they do
not believe it is worth publishing and hope a more clever proof can be found.

######  Conjecture 4.

One firefighter can prevent the pyro from burning any vertex distance $7$ from
the original burned vertex $(0,0)$ on the infinite Cartesian grid.

In the (original) Firefighter problem, two firefighters are necessary to
contain a fire on the 2-dimensional Cartesian grid, but are not sufficient to
contain a fire on the 3-dimensional Cartesian grid: for the 3-dimensional
Cartesian grid $5$ firefighters are necessary [11].

######  Question 5.

What is the minimum integer $f$ such that if firefighters protect $f$ vertices
at each step, the firefighters can contain the pyro on a 3-dimensional
Cartesian grid.

##  4 The infinite strong grid

###  4.1 The Pyro game on an infinite strong grid

In this section, we show that in the Pyro game, two firefighters (protecting
two vertices at each step $t>0$) suffice to contain a fire on the strong grid.
To do this, we provide a simple algorithm to describe the vertices protected
at each step $t>0$ that leave the pyro fire unable to burn a vertex distance
$29$ from the vertex $(0,0)$ burned at $t=0$. Like Algorithm 2, the simplicity
of the algorithm results from giving the pyro extra “power” for the first $25$
steps and by reducing the firefighters “power” at every step. In particular,
for the first $25$ steps, we allow the pyro to burn from each burned vertex to
every neighbouring vertex. We additionally impose restrictions on the
firefighters and allow them to only protect vertices that are exactly distance
$29$ from the original burned vertex.

Let $T$ be the set of vertices $(x,y)$ where

  * •

$x=\pm 29$ and $(23\leq y\leq 29)\vee(-29\leq y\leq-23)$; or

  * •

$y=\pm 29$ and $(23\leq x<29)\vee(-29<x\leq 23)$.

Set $T$ is partially illustrated in Figure 3 by the shaded area. The algorithm
below dictates that that during each of the first $26$ steps, the firefighters
protect $2$ of the $52$ vertices of $T$ and for $t>26$, describes how the
firefighters protect vertices of set
$D=\\{(x,y):dist((x,y),(0,0))=29\\}\backslash T$.

Figure 3: A subset of vertices of $T$ on the strong grid.

######  Algorithm 6.

The Pyro game with two firefighters on an infinite strong grid.

1) At step $0$, the pyro chooses a vertex to burn; label this vertex $(0,0)$.

2) For $1\leq t\leq 25$, at step $t$, the firefighters protect any two
unprotected vertices of $T$ and then the fire burns from every vertex distance
$t-1$ from the origin, to every vertex distance $t$ from the origin.

3) At the beginning of step $26$, the firefighters protect the last two
unprotected vertices of $T$.

4) For $t\geq 26$, during step $t$, the pyro will choose one burning vertex
$(x,y)$ and spread from that vertex to all unprotected unburned neighbours.
Observe that $(x+i,y)\oplus(x,y+i)\in D$ for some
$i\in\\{-4,-3,-2,-1,1,2,3,4\\}$ since $|x|\geq 25$ and $|y|\geq 25$. During
during step $t+1$, the firefighters will proceed as follows:

a) If $(x,y+i)\in D$, the firefighters protect two unprotected vertices of

$A_{t}=\\{(x-2,y+i),(x-1,y+i),(x,y+i),(x+1,y+i),(x+2,y+i)\\}$

that are closest to $(x,y+i)$, arbitrarily breaking ties. (If there is only
one unprotected vertex in $A_{t}$, the firefighters protect that vertex and an
arbitrary vertex of $D$; and if there are no unprotected vertices in $A_{t}$,
the firefighters protect two arbitrary vertices of $D$.)

b) If $(x+i,y)\in D$, the firefighters protect two unprotected vertices of

$B_{t}=\\{(x+i,y-2),(x+i,y-1),(x+i,y),(x+i,y+1),(x+i,y+2)\\}$

that are closest to $(x+i,y)$, arbitrarily breaking ties. (If there is only
one unprotected vertex in $B_{t}$, the firefighters protect that vertex and an
arbitrary vertex of $D$; and if there are no unprotected vertices in $B_{t}$,
the firefighters protect arbitrary vertices of $D$.)

We next prove the algorithm will prevent any vertex distance $29$ from being
burned.

######  Theorem 7.

By following Algorithm 6, in the Pyro game two firefighters suffice to contain
a fire on the strong grid.

###### Proof.

We will use Algorithm 6 to prove a stronger result, namely that if the pyro is
given additional “power” to burn from each burning vertex to each neighbouring
vertex during the first $25$ steps, two firefighters can prevent the pyro from
burning any vertex distance $29$ from the original burned vertex.

Consider any step $t\geq 26$: during step $t$, the pyro will choose one
burning vertex $(x,y)$ and burn from $(x,y)$ to all neighbouring vertices.
Since we assumed that every vertex within distance $26$ of the original burned
vertex $(0,0)$ is burned by the end of step $26$, we know that either
$(x,y+i)\in D$ or $(x+i,y)\in D$ for some $i\in\\{-4,-3,-2,-1,1,2,3,4\\}$. And
from the definitions of $T$ and $D$, exactly one of $(x,y+i)$, $(x+i,y)$ is in
$D$.

Consider 4) a) of Algorithm 6, where $(x,y+i)\in D_{t}$ and wlog, suppose
$i\in\\{1,2,3,4\\}$.

If $i=4$, then after the firefighters have moved during step $t+1$, clearly at
least two vertices of $A_{t}$ have been protected.

If $i=3$, then consider the neighbour(s) of $(x,y)$ that were burned at some
step(s) prior to $t$. The Pyro burned from least one of
$(x-1,y),(x-1,y+1),(x,y+1),(x+1,y+1),(x+1,y),(x+1,y-1),(x,y-1),(x-1,y-1)$ at
an earlier step. But this would mean at least one of
$(x-1,y+3),(x,y+3),(x+1,y+3)$ was protected at an earlier step. Thus, after
the firefighters have protected vertices during step $t+1$, vertices
$(x-1,y+3),(x,y+3),(x+1,y+3)$ have all been protected.

If $i=2$, then consider the neighbour(s) of $(x,y)$ that were burned at some
step(s) prior to $t$. The Pyro burned from least one of
$(x-1,y),(x-1,y+1),(x,y+1),(x+1,y+1),(x+1,y),(x+1,y-1),(x,y-1),(x-1,y-1)$ at
an earlier step; call this vertex $(x^{\prime},y^{\prime})$ and suppose it was
burned at step $t^{\prime}$. But this would mean at least two of $A_{t}$ were
protected at an earlier step than $t+1$. And, the Pyro burned some vertex in
the neighbourhood of $(x^{\prime},y^{\prime})$ at some step
$t^{\prime\prime}<t^{\prime}$. If $x^{\prime\prime}\in\\{x-1,x,x+1\\}$ then at
least two vertices of $A_{t}$ were protected at step $t^{\prime\prime}+1$. If
$x^{\prime\prime}\in\\{x-2,x+2\\}$, then at least one of $(x-2,y+i)$,
$(x-2,y+i)$ was protected at step $t^{\prime\prime}+1$. In any event, after
the firefighters protect vertices during step $t+1$, every vertex of $A_{t}$
has been protected.

If $i=1$, then consider the neighbour(s) of $(x,y)$ that were burned at some
step(s) prior to $t$. The Pyro burned from least one of
$(x-1,y),(x+1,y),(x+1,y-1),(x,y-1),(x-1,y-1)$ at an earlier step; call this
vertex $(x^{\prime},y^{\prime})$ and suppose it was burned at step
$t^{\prime}$. But this would mean at least two of $A_{t}$ were protected by
step $t^{\prime}+1$. And, the Pyro burned some vertex (call it
$(x^{\prime\prime},y^{\prime\prime})$) in the neighbourhood of
$(x^{\prime},y^{\prime})$ at some step $t^{\prime\prime}<t^{\prime}$. If
$x^{\prime\prime}\in\\{x-1,x,x+1\\}$ then at least two vertices of $A_{t}$
were protected at step $t^{\prime\prime}+1$. If
$x^{\prime\prime}\in\\{x-2,x+2\\}$ then at least one of $(x-2,y+i),(x+2,y+i)$
was protected at step $t^{\prime\prime}+1$. In any event, after the
firefighters protect vertices during step $t+1$, every vertex of $A_{t}$ has
been protected.

Thus, we can see that if the pyro burns from some vertex $(x,y)$ at step $t$
where $i\in\\{-2,-1,1,2\\}$, then the pyro cannot burn a vertex of $D$ in step
$t+1$. Since 4) b) of Algorithm 6 is extremely similar to a), we omit the
remainder of the proof to avoid a redundant explanation.∎

Though two firefighters suffice to contain a fire on the strong grid, it
remains unknown as to whether one firefighter suffices. We conjecture it is
not possible.

######  Conjecture 8.

In the Pyro game, one firefighter cannot contain a fire on the strong grid.

###  4.2 The Firefighter problem on an infinite strong grid

In Section 4.1, we considered the Pyro game on the infinite strong grid. In
order to better understand the differences between the Pyro game and the
Firefighter problem, we next consider the Firefighter problem on the infinite
square grid. We prove that four, but not three firefighters can contain a fire
on the infinite strong grid.

######  Theorem 9.

In the Firefighter problem, firefighters protecting three vertices at each
step cannot contain a fire on the infinite strong grid.

###### Proof.

For a contradiction, suppose firefighters protecting three vertices at each
step suffice to contain a fire on the infinite strong grid. Note that once the
fire can no longer spread, any protected vertex $(x,y)$ that is not adjacent
to a burned vertex was unnecessarily protected: if $(x,y)$ had not been
protected, the fire would still have been contained. Additionally, note that
any protected vertex $(x,y)$ that is adjacent to a burned vertex but not an
unprotected saved vertex was also unnecessarily protected: if $(x,y)$ had not
been protected, the fire would still have been contained. Thus, we may
further, assume the firefighters protect a minimal set of vertices to contain
the fire. Consequently, once the fire has been contained, every protected
vertex is adjacent to at least one unprotected saved vertex and at least one
burned vertex. Let $S$ be a minimal set of vertices that can be protected in
order to contain the fire.

Suppose that once the fire has been contained, $(x,y),(x,y+1),(x+1,y)$ are all
in $S$ and $(x+1,y+1)$ was saved but not in $S$. Then during the step where
$(x,y)$ was protected, the firefighters could alternately have protected
$(x+1,y+1)$ and still contained the fire. Thus,
$S\backslash\\{(x,y)\\}\cup\\{(x+1,y+1)\\}$ is a minimal set of vertices that
can be protected in order to contain the fire. We refer to the action of
updating $S$ to $S\backslash\\{(x,y)\\}\cup\\{(x+1,y+1)\\}$ as “popping a
corner”, as illustrated in Figure 4.

Figure 4: An example of a set of protected (white) vertices before a corner is
popped.

Similarly, updating $S$ in each of the three ways below will also be referred
to as “popping a corner”:

  * •

if once the fire has been contained, $(x,y),(x,y+1),(x-1,y)$ are all in $S$
and $(x-1,y+1)$ was saved but not in $S$ then
$S\backslash\\{(x,y)\\}\cup\\{(x-1,y+1)\\}$ is a minimal set of vertices that
can be protected in order to contain the fire.

  * •

if once the fire has been contained, $(x,y),(x,y-1),(x-1,y)$ are all in $S$
and $(x-1,y-1)$ was saved but not in $S$ then
$S\backslash\\{(x,y)\\}\cup\\{(x-1,y-1)\\}$ is a minimal set of vertices that
can be protected in order to contain the fire.

  * •

if once the fire has been contained, $(x,y),(x,y-1),(x+1,y)$ are all in $S$
and $(x-1,y-1)$ was saved but not in $S$ then
$S\backslash\\{(x,y)\\}\cup\\{(x-1,y-1)\\}$ is a minimal set of vertices that
can be protected in order to contain the fire.

If we iteratively apply the means of updating the set of protected vertices,
effectively “popping all the corners”, then obviously the set of protected
vertices will form a rectangle. More precisely, this implies there exists a
strategy for the firefighters contain the fire so that the following sets of
vertices are protected:

$\\{(u,\ell_{1}):k_{2}\leq u\leq k_{1}\\},~{}~{}\\{(u,-\ell_{2}):-k_{2}\leq
u\leq k_{1}\\},$
$\\{(-k_{2},v):-\ell_{2}<v<\ell_{1}\\},~{}~{}\\{(k_{1},v):-\ell_{2}<v<\ell_{1}\\}$

for some non-negative integers $k_{1},\ell_{1},k_{2},\ell_{2}$.

We next obtain a contradiction and show the firefighters cannot actually
contain the fire. Without loss of generality, suppose $k_{2}\geq k_{1}$,
$\ell_{2}\geq\ell_{1}$, and $\ell_{1}\geq k_{1}$.

First, suppose $\ell_{1}\leq k_{2}$ and consider the vertices burned and
protected by the end of step $t=\ell_{1}$. To prevent the fire from burning a
vertex with $x$-coordinate $k_{1}+1$ or a vertex with $y$-coordinate
$\ell_{1}+1$, the firefighters must protect at least $2\ell_{1}+1$ vertices
with $x$-coordinate $\ell_{1}$ and
$k_{1}+\min\\{\ell_{1},k_{2}\\}=k_{1}+\ell_{1}$ vertices with $y$-coordinate
$\ell_{1}$ by the end of step $t=\ell_{1}$. However, this yields a total of at
least $3\ell_{1}+k+1+1$ vertices and provides a contradiction as the
firefighters can only protect $3\ell_{1}$ vertices by the end of step
$\ell_{1}$.

Second, suppose $k_{2}<\ell_{1}$. Then $k_{1}\leq k_{2}<\ell_{1}\leq\ell_{2}$.
To prevent the fire from burning a vertex with $x$-coordinate $-k_{2}-1$ or
$k_{1}+1$, the firefighters must protect at least $2k_{2}+1$ vertices with
$x$-coordinate $-k_{2}$ and $2k_{2}+1$ vertices with $x$-coordinate $k_{1}$.
This yields a total of at least $4k_{2}+2$ protected vertices and provides a
contradiction as the firefighters can protect only $3k_{2}$ vertices by the
end of step $k_{2}$.∎

It is easy to see that four firefighters suffice to contain a fire on the
infinite strong grid and this is illustrated in Figure 5. The square vertex
indicates the original burned vertex; the white vertices with numbers indicate
protected vertices and the step in which each vertex is protected. Thus, we
can see that four firefighters can contain a fire by the end of step $t=8$.

######  Corollary 10.

Four firefighters suffice to contain a fire on the infinite strong grid.

Figure 5: Containing a fire by protecting four vertices at each step.

## References

  * [1] E. R. Berlekamp, J. H. Conway, R. K. Guy, _Winning ways for your mathematical plays_ , Vol. 2, Academic Press Inc [Harbout Brace Jovanovich Publishers], London, 1982.
  * [2] C. Blum, M.J. Blesa, C. García-Martinez, F.J. Rodriguez, M. Lozano (2014) The Firefighter Problem: Application of Hybrid Ant Colony Optimization Algorithms. In: Blum C., Ochoa G. (eds) Evolutionary Computation in Combinatorial Optimisation. EvoCOP 2014. Lecture Notes in Computer Science, vol 8600. Springer, Berlin, Heidelberg.
  * [3] A. Bonato, M.E. Messinger, P. Pralat, Fighting constrained fires in graphs, Theoretical Computer Science 434 (2012) 11-22.
  * [4] J. H. Conway, _The Angel Problem_ , Games of No Chance (Berkley, CA, 1994). Cambridge Univ. Press, Cambridge, 1996, pp. 3-12.
  * [5] O.N. Feldham, R. Hod, $3/2$ firefighters are not enough, Discrete Applied Mathematics 161 (2013) 301-306.
  * [6] F.V, Fomin, P. Heggernes, E.J. van Leeuwen, The firefighter problem on graph classes, Theoretical Computer Science 613 (2016) 38-50.
  * [7] C. García-Martinez, C. Blum, F.J. Rodriguez, M. Lozano, The firefighter problem: Empirical results on random graphs, Computers & Operations Research 60 (2015) 55-66.
  * [8] M. Gardner, _Mathematical games: Cram, crosscram, and quadraphage: new games having elusive winning strategies_ , Sci. Amer. 230 (1974), no. 2, 106–108.
  * [9] T. Gavenc̆iak, J. Kratochvíl, P. Prałat, Firefighting on square, hexagonal, and triangular grids, Discrete Mathematics 337 (2014) 142-155.
  * [10] B.L. Hartnell, _Firefighter! An Application of Domination_ , presentation at the Twentieth Conference on Numerical Mathematics and Computing (University of Manitoba, 1995).
  * [11] M. Develin, S.G. Hartke, Fire containment in grids of dimensions three and higher, Discrete App. Math. 155(17) (2007) 2257-2268.
  * [12] M. Kutz, The Angel Problem, Positional Games, and Digraph Roots: Strategies and Complexity, PhD Thesis, FU Berlin 2004.
  * [13] S. Finbow, G. MacGillivray, The firefighter problem: a survey of results, directions and questions, Australasian Journal of Combinatorics 43 (2009) 57-77.
  * [14] G. MacGillivray, P. Wang, On the firefighter problem, J. Combin. Math. Combin. Computing 47 (2003) 83-96.
  * [15] M.E. Messinger, Average firefighting on infinite grids, Australasian Journal of Combinatorics, 41 (2008) 15-28.
  * [16] K.L. Ng, P. Raff, A generalization of the firefighter problem on $\mathbb{Z}\times\mathbb{Z}$, Discrete Appl. Math. 156(5) (2008) 730-745.
  * [17] P. Wang, S. Moeller, Fire control on graphs, J. Combin. Math. Combin. Computing 41 (2002) 19-34.


# Weather Classification: A new multi-class dataset, data augmentation
approach and comprehensive evaluations of Convolutional Neural Networks
††thanks: This work is supported by the UK Engineering and Physical Sciences
Research Council through grants EP/R02572X/1 and EP/P017487/1

Jose Carlos Villarreal Guerra1, Zeba Khanam1, Shoaib Ehsan1, Rustam Stolkin2,
Klaus McDonald-Maier1 1Embedded and Intelligent Systems Lab, University of
Essex
2Extreme Robotics Lab (ERL), University of Birmingham
{ 1zeba.khanam, 1sehsan, 1kdm<EMAIL_ADDRESS>1
<EMAIL_ADDRESS>2<EMAIL_ADDRESS>
###### Abstract

Weather conditions often disrupt the proper functioning of transportation
systems. Present systems either deploy an array of sensors or use an in-
vehicle camera to predict weather conditions. These solutions have resulted in
incremental cost and limited scope. To ensure smooth operation of all
transportation services in all-weather conditions, a reliable detection system
is necessary to classify weather in wild. The challenges involved in solving
this problem is that weather conditions are diverse in nature and there is an
absence of discriminate features among various weather conditions. The
existing works to solve this problem have been scene specific and have
targeted classification of two categories of weather. In this paper, we have
created a new open source dataset consisting of images depicting three classes
of weather i.e rain, snow and fog called RFS Dataset. A novel algorithm has
also been proposed which has used super pixel delimiting masks as a form of
data augmentation, leading to reasonable results with respect to ten
Convolutional Neural Network architectures.

###### Index Terms:

Weather Classification , Convolutional Neural Network , Superpixels, Data
Augmentation

##  I Introduction

Time and again unfortunate accidents due to inclement weather conditions
across the globe have surfaced. Ship collision, train derailment, plane crash
and car accidents are some of the tragic incidents that have been a part of
the headlines in recent times. This grave problem of safety and security in
adverse conditions has drawn the attention of the society and numerous studies
have been done in past to expose the vulnerability of functioning of
transportation services due to weather conditions [1]. In past, weather-
controlled driving speeds and behaviour have been proposed [2]. With the
advancement in technology and emergence of a new field, intelligent
transportation, automated determination of weather condition has become more
relevant. Present systems either rely on series of expensive sensors or human
assistance to identify the weather conditions [3], [4], [5]. Researchers, in
recent era have looked at various economical solutions. They have channelled
their research in a direction where computer vision techniques have been used
to classify the weather condition using a single image. The task of assessing
the weather condition from a single image is a straightforward and easy task
for humans. Nevertheless, this task has a higher difficulty level for an
autonomous system and designing a decent classifier of weather that receives
single images as an input would represent an important achievement.

The work described in this paper translates to two contributions to the field
of weather classification. The first one is exploring the use of superpixel
masks as a data augmentation technique, considering different Convolutional
Neural Network (CNN) architectures for the feature extraction process when
classifying outdoor scenes in a multi-class setting using general-purpose
images. The second contribution is the creation of a new, open source dataset,
consisting of images collected online that depict scenes of three weather
conditions, called Rain Fog Snow (RFS) dataset.

The paper has been organized into six sections. In the section I, a brief
introduction to the topic has been presented. This has been followed by the
section II which narrates the recent advances made in this field. Section III
presents detail description of proposed dataset ’RFS’. Section IV mentions the
corresponding background on the use of superpixel masks and details of chosen
architectures for evaluation. Section IV also reports description of the
methodology, emphasizing on the employed pipeline and other parameters that
were used. Section V evaluates the results of experiment and inferences that
can be drawn. Finally, section VI sheds a light on conclusions obtained that
can guide future work that is relevant to the topic.

##  II Related Work

In recent years, important contributions have been made as an attempt to solve
the weather classification problem. Many of these recognisable attempts target
the problem from perspective of weather classification for traffic purposes
were limited to single adverse condition like rain([6], [7], [8],[9]) and
fog([10], [11], [12]). The dataset used to train the classifier in this
problem contains images captured using on board camera of various weather
conditions on roads and highways. This implies that they share a set of
features that are exclusive to specific purpose of driving assistance on road
and cannot not be generalised for the classification of images with different
backgrounds and viewpoint.

The generalization of this task has added to complexity of the problem as it
is hard to find a consistent set of features that can be extracted in all the
relevant images. Differing contributions have been made on the most relevant
features for weather classification. Lu et al. [13] proposed a two-class
weather classifier which classified images based on five features (Sky, Haze,
Contrast, Reflection and Shadow). This work was extended by the authors by
contacting CNN features in the feature vector. Similarly, Zhang and Ma [14]
rely on manual feature identification and extraction for the development of
their weather classifier. They use global and local features to represent the
images. The authors refer to local features, which are the set of
characteristics that are used to represent a given type of weather, and thus
would not be present in images depicting a different kind of weather. For a
more generalised visualisation, they use global features which are presented
as general characteristics of images that could be present in images with any
kind of weather.

Convolutional Neural Networks (CNNs) have been used in recent works for image
classification. Krizhevsky et al. [15] implemented the special architecture of
CNNs for image classification, taking advantage of the advances in computing
power needed for its training and overall performance. Their implementation
showed the capabilities of an image classifier with a built-in feature
extraction based on supervised learning [15], instead of the manual extraction
of features used in other machine learning applications.

In the field of weather classification, CNNs have been used in [16] and [17].
In their paper, Elhoseiny et al. [16] created a network based on the work by
Krizhevsky et al. [15] for the categorization of images between two possible
classes. Their contribution represented an insightful approach that adopted
the technology being used for general purposes into a highly specific
application, proving that it can achieve exceptional results. Lu et al. [18]
extended their work of two-class weather recognition by adding CNN features
used by [16]. Similarly, Zhu et al. [17] explored an implementation that has
proven successful for the task of image classification, which is the
architecture known as GoogLeNet, proposed in [19]. This implementation of CNNs
had more layers than its counterparts at the moment of its proposal and
achieved better results in the experimentation carried out in [17] used on a
collection of weather images generated by the same team. Di Lin et al. [20]
proposed a deep learning framework named region selection and concurrency
model (RSCM) which used regional cues to predict the weather condition.

##  III RFS Dataset

Figure 1: Sample images of all three categories of RFS Weather Dataset.

For the purposes of creating an open source dataset that can potentially
contribute to future efforts in the field of computer vision, the images of
interest containing Creative Commons [21] license retrieved from Flickr [22],
Pixabay[23] and Wikimedia Commons[24] have been used. Different images are
subject to different types of licenses; however, a common requirement is to
give attribution to the author. This premise as a method to collect images is
a fair way to build a dataset intended to be shared while respecting the
producers of the content of interest. Unfortunately, the amount of images with
the Creative Commons licenses are considerably smaller than the number of
images with reserved copyright, leading to potentially smaller datasets. The
collection of images created as part of this work composes the RFS Weather
Dataset111RFS can be accessed online using the link:
https://github.com/ZebaKhanam91/SP-Weather , named after the three categories
that it includes. Figure 1 shows a sample of the images contained in RFS
Weather Dataset.

###  III-A Images of Fog

The task to look for images depicting foggy weather was relatively easy, as
the different image hosting web sites have a decent collection of this type of
pictures. However, the use of synonyms, as well as terms in other languages
was required to find the total number images that compose the foggy category.
Another set of useful search terms consists on looking for locations (cities
or towns) that are characterised by foggy weather, and use these as the tags
to look for. The foggy category of the RFS Weather Dataset contains 1100
images.

###  III-B Images of Rain

Collecting images of rainy weather condition was a challenge. Since many of
the images which were tagged as “rainy” on the platforms were representation
of raindrops on glass scene and indoor activities for rainy days. However,
1100 quality images with landscapes and urban scenes of rainy days are
represented in this category of the dataset. To gather the images, the first
strategy is to use the word ”rainy” as the search term, collect the images and
then move on to related words like ”rain” or ”deluge”, and finally use these
terms in other languages.

###  III-C Images of Snow

The category for images showing snowy outdoor scenes was built using terms in
English, French and Spanish. The terms included ”snowy” and ”snow”, and
returned a decent amount of images that are included in the dataset. From the
returned images, the 1100 most representative images are included in the RFS
Weather Dataset.

##  IV Methodology

Cognitive psychology has been inspiration of many computer vision algorithms.
In order to contribute towards the development of the field, and particularly
the weather classification task, an effort is presented as an inquiry into the
effect that superpixel delimiting masks on images have on the performance of
weather classification. Based on the recent success of Convolutional Neural
Networks in the field of Computer Vision, different conceptions of this
technology are used in the work described here. The purpose is to determine if
any of these architectures can benefit from the use of superpixel masks.

The categories of interest for this contribution are sunny, cloudy, foggy,
rainy and snowy images. For the sunny and cloudy categories, Lu et al. [13]
developed a dataset as a part of their work. This dataset contains images from
other datasets and images available online and labelled as part of their
contribution. This dataset was made available on the web page associated with
their paper. The images for the other categories are those belonging to RFS
weather dataset. Since RFS weather Dataset contains 1100 images for each of
its categories, 1100 images were taken from the categories in Lu et al.
dataset, having a total of 5500 images distributed in five categories. To
create a partition of the images for the Support Vector Machine classifier
training and testing process, 70% of the images are used for the training
phase, while 30% is used for the testing phase. However, the classifier is
trained over each of the five different categories, which means that each
class had a negative counterpart with images that served as an example of what
the category does not look like (composed of images from the other classes of
the combined datasets). With this dataset setting, the binary classifier for
each category determine if a given image represents or not the current class.

###  IV-A Pipeline

The pipeline used for the work described in this paper is based on the work by
Kalliatakis et al. in [10]. A visual representation of the pipeline is shown
in Figure 2. There are two possible paths in the pipeline, either using
superpixel masks or using the raw images directly. In the first mode of
operation, the images are passed through a module that calculates the
superpixels, generates the mask in a colour and applies it over the image,
just as shown in Figure 3. The images, enhanced with supeprixel mask if used,
are divided into four partitions corresponding to positive training, positive
testing, negative training, and negative testing. Then, the matdeeprep
function [10], which uses pre-trained Convolutional Neural Network models, is
used to extract deep features from the images in all the partitions. Finally,
the features are used to train and test a binary Support Vector Machine
classifier.

Figure 2: Project Pipeline

###  IV-B Software Implementation

The pipeline is implemented in MATLAB, coupled with Caffe [25]. The Matdeeprep
function [26] is executed on top of Caffe for the use of pre-trained models
for the extraction of features that are intended to be used in a classifier.
For the Support Vector Machine part of the pipeline, a special library of
Computer Vision algorithms was used, called VLFeat and presented in [27].

###  IV-C Experimentation

The classifier was trained and tested on images of each category, which are
cloudy, foggy, rainy, snowy, and sunny. For each of the categories, 770 were
used as positive training and testing set each, and 330 images were used for
negative training and testing each. After performing the different runs of the
experiment, the mean Average Precision (mAP) was calculated for each of the
models trained with the results for each of the categories. The
experimentation proceeded in five different settings: using the raw images,
images with 25,50,75 and 100 superpixel masks.

Figure 3: A sunny image with overlayed boundaries of 25 superpixel mask

##  V Results

TABLE I: Results from CNN evaluations Model | 0 SP | 25 SP | 50 SP | 75SP | 100 SP
---|---|---|---|---|---
CaffeNet | 0.7591 | 0.7568 | 0.7542 | 0.7564 | 0.7573
PlacesCNN | 0.7627 | 0.7401 | 0.7311 | 0.7322 | 0.7335
ResNet 50 | 0.7767 | 0.7851 | 0.7957 | 0.8007 | 0.8070
ResNet 101 | 0.7681 | 0.7643 | 0.7614 | 0.7698 | 0.7756
ResNet 152 | 0.7504 | 0.7584 | 0.7538 | 0.7549 | 0.7519
VGG_CNN_F | 0.7134 | 0.7224 | 0.7252 | 0.7309 | 0.7201
VGG_CNN_M | 0.6849 | 0.6900 | 0.6947 | 0.6984 | 0.7006
VGG_CNN_S | 0.7060 | 0.7202 | 0.7188 | 0.7229 | 0.7272
VGGNet16 | 0.7194 | 0.7203 | 0.7252 | 0.7244 | 0.7218
VGGNet19 | 0.6948 | 0.7008 | 0.7041 | 0.7111 | 0.7167

After the trial runs, the results show that the overall mAP for all of the
models and settings is between 68% and 81%. Table I shows the complete results
of the experimentation process. The overall best classification was the ResNet
50 architecture for all of the settings of the superpixel masks. The three
variations of the residual networks (ResNet) used in the experimentation were
among the four top performing models in the four different settings. These
results are a good indication that the optimisation achieved by the inclusion
of residual methods learning with shortcut connections [28] has a positive
effect in the overall task of weather classification, and it can benefit
slightly from the use of superpixel masks as data augmentation. The results of
this contribution are consistent with [28], paper in which Residual Networks
are described as the winners of the 2015 ILSVRC competition, having a smaller
error than GoogLeNet and the VGG networks. Residual Networks are thus not only
successful in arbitrary image recognition, but can also work well as a
solution to weather classification problem. Another notable fact that is
evident with the results shown in Table I is increase in performance between
the experimental setting involving raw images and the ones involving
superpixel masks for all models except for PlacesCNN model and CaffeNet model.

Figure 4: CNN Evaluations for Cloudy Category

Figure 5: CNN Evaluations for Rainy Category

Figure 6: CNN Evaluations for Foggy Category

Figure 7: CNN Evaluations for Snowy Category

Figure 8: CNN Evaluations for Sunny Category

The analysis of results category wise (Figure 4-8) indicate that the best
architecture to handle the weather classification problem are three ResNet
architectures except for sunny category where VGG_CNN_M performs best. As
described in [28], it is possible to use this type of networks with different
depths. Concluding the potential of this type of network, draws attention for
the possibility of more experimentation using them with different and larger
datasets. Although certain improvement is noticeable, it is evident that
computational cost will be incurred on calculation of superpixel masks. The
trade off between increase precision and computational cost is worth pursuing
in future.

##  VI Conclusion

This paper explores the possibility of using superpixel masks as a form of
data augmentation that improves the performance of a classifier in the context
of weather classification. Also, a fair method for building datasets from
online content is showcased, giving credit that corresponds to the creators of
content. Proposed dataset is also hybrid in nature as images for two weather
classes have been taken from a benchmark dataset. This allows persistent
problem of biases in computer vision datasets to be tackled.
The specific field of computer vision known as weather classification is still
evolving and worthy proposals are still being made to improve the baseline. An
opportunity to advance the field even further lies in the adoption of new
techniques and tools that have been used to improve other fields. To achieve
this, it is necessary to recognise that weather is a phenomenon that is a
complex phenomena where semantic labelling of images can be a challenging task
. A single image can encompass multiple weathers for instance partly cloudy.
To exploit all the information that can be extracted from a single outdoor
image, considering uncertainty as an opportunity rather than a problem is an
important step. As Rutkowski states in [29], different techniques of computer
science sometimes can be combined to constitute new and better proposals,
which might lead to implementations like neuro-fuzzy systems to tackle the
weather classification problem.

## References

  * [1] Jean Andrey, Brian Mills, Mike Leahy, and Jeff Suggett,  “Weather as a chronic hazard for road transportation in canadian cities,”  Natural Hazards, vol. 28, no. 2-3, pp. 319–343, 2003.
  * [2] P Rama and Anna Schirokoff,  “Effects of weather-controlled variable speed limits on injury accidents,”  in European Congress on Intelligent Transportation Systems and Services, 4th, 2004, Budapest, Hungary, 2004.
  * [3] WALTER I CHRISTENSEN JR and Reid A Bryson,  “An investigation of the potential of component analysis for weather classification,”  Monthly Weather Review, vol. 94, no. 12, pp. 697–709, 1966.
  * [4] Jeffrey A Nystuen and Harry D Selsor,  “Weather classification using passive acoustic drifters,”  Journal of Atmospheric and Oceanic Technology, vol. 14, no. 3, pp. 656–666, 1997.
  * [5] Reiner Schnur and Dennis P Lettenmaier,  “A case study of statistical downscaling in australia using weather classification by recursive partitioning,”  Journal of Hydrology, vol. 212, pp. 362–379, 1998.
  * [6] Martin Roser and Frank Moosmann,  “Classification of weather situations on single color images,”  in Intelligent Vehicles Symposium, 2008 IEEE. IEEE, 2008, pp. 798–803.
  * [7] Hiroyuki Kurihata, Tomokazu Takahashi, Ichiro Ide, Yoshito Mekada, Hiroshi Murase, Yukimasa Tamatsu, and Takayuki Miyahara,  “Rainy weather recognition from in-vehicle camera images for driver assistance,”  in Intelligent Vehicles Symposium, 2005. Proceedings. IEEE. IEEE, 2005, pp. 205–210.
  * [8] Aurelien Cord and Nicolas Gimonet,  “Detecting unfocused raindrops: In-vehicle multipurpose cameras,”  IEEE Robotics & Automation Magazine, vol. 21, no. 1, pp. 49–56, 2014.
  * [9] Andreas Kuehnle,  “Method and system for weather condition detection with image-based road characterization,” May 7 2013,  US Patent 8,436,902.
  * [10] Mario Pavlic, Gerhard Rigoll, and Slobodan Ilic,  “Classification of images in fog and fog-free scenes for use in vehicles,”  in Intelligent Vehicles Symposium (IV), 2013 IEEE. IEEE, 2013, pp. 481–486.
  * [11] Rachid Belaroussi and Dominique Gruyer,  “Convergence of a traffic signs-based fog density model,”  in Intelligent Transportation Systems (ITSC), 2015 IEEE 18th International Conference on. IEEE, 2015, pp. 783–787.
  * [12] Mario Pavlic,  “Method for fog detection,” July 5 2016,  US Patent 9,384,401.
  * [13] Cewu Lu, Di Lin, Jiaya Jia, and Chi-Keung Tang,  “Two-class weather classification,”  in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp. 3718–3725.
  * [14] Zheng Zhang and Huadong Ma,  “Multi-class weather classification on single images,”  in Image Processing (ICIP), 2015 IEEE International Conference on. IEEE, 2015, pp. 4396–4400.
  * [15] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton,  “Imagenet classification with deep convolutional neural networks,”  in Advances in neural information processing systems, 2012, pp. 1097–1105.
  * [16] Mohamed Elhoseiny, Sheng Huang, and Ahmed Elgammal,  “Weather classification with deep convolutional neural networks,”  in Image Processing (ICIP), 2015 IEEE International Conference on. IEEE, 2015, pp. 3349–3353.
  * [17] Ziqi Zhu, Li Zhuo, Panling Qu, Kailong Zhou, and Jing Zhang,  “Extreme weather recognition using convolutional neural networks,”  in Multimedia (ISM), 2016 IEEE International Symposium on. IEEE, 2016, pp. 621–625.
  * [18] C. Lu, D. Lin, J. Jia, and C. K. Tang,  “Two-class weather classification,”  IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 39, no. 12, pp. 2510–2524, Dec 2017.
  * [19] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, Andrew Rabinovich, et al.,  “Going deeper with convolutions,”  Cvpr, 2015.
  * [20] Di Lin, Cewu Lu, Hui Huang, and Jiaya Jia,  “Rscm: Region selection and concurrency model for multi-class weather recognition,”  IEEE Transactions on Image Processing, vol. 26, no. 9, pp. 4154–4167, 2017.
  * [21] Creative Commons,  “When we share, everyone wins - creative commons,” 2018.
  * [22] Flickr,  “Find your inspiration. flickr,” 2018.
  * [23] Pixbay,  “Free images - pixbay,” 2018.
  * [24] Wikimedia Commons,  “Main page — wikimedia commons, the free media repository,” 2017,  [Online; accessed 5-February-2018].
  * [25] Yangqing Jia, Evan Shelhamer, Jeff Donahue, Sergey Karayev, Jonathan Long, Ross Girshick, Sergio Guadarrama, and Trevor Darrell,  “Caffe: Convolutional architecture for fast feature embedding,”  in Proceedings of the 22nd ACM international conference on Multimedia. ACM, 2014, pp. 675–678.
  * [26] Grigorios Kalliatakis, Shoaib Ehsan, Maria Fasli, Ales Leonardis, Juergen Gall, and Klaus D McDonald-Maier,  “Detection of human rights violations in images: Can convolutional neural networks help?,”  arXiv preprint arXiv:1703.04103, 2017.
  * [27] Andrea Vedaldi and Brian Fulkerson,  “Vlfeat: An open and portable library of computer vision algorithms (2008),” 2012.
  * [28] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
  * [29] Leszek Rutkowski,  Flexible neuro-fuzzy systems: structures, learning and performance evaluation, vol. 771,  Springer Science & Business Media, 2006.