\section{Proofs for \cref{sec:main}}
\subsection{Proof of \cref{lemma:next}}
We first observe the following helpful result:
\begin{lemma}\label{obs:nextins}
	Let $\partial = \ins{\zeta}{u}$ and let $x \leadsto_{w} y$ for $x,y \in D$. We have that $x \not\leadsto_{w'} y$ if and only if $x<u<y$.
\end{lemma}
\begin{proof}
	Let $\zeta \in \Sigma$, if we perform the update $\ins{\zeta}{u}$ on $\mathcal{W}$ where $x<u<y$ then it follows that there exists some $z$ such that $w'(z) \neq \varepsilon$ and $x<z<y$. Therefore it cannot be the case that $x \leadsto_{w'} y$, so $x \not\leadsto_{w'} y$.

	If it is not the case that $x<u<y$ then it cannot be that there exists some $z \in D$ such that $x<z<y$ where $w'(z) \neq \varepsilon$. Therefore, if $x \leadsto_{w} y$ and $\partial = \ins{\zeta}{u}$ then $x \not\leadsto_{w'} y$ if and only if $x<u<y$.
\end{proof}
\subsubsection{Actual proof of \cref{lemma:next}}
\input{proof-nextsymbol.tex}

\subsection{Proof of \cref{lemma:eqsubstr}}
We first observe two results which help us in the actual proof of \cref{lemma:eqsubstr}:

\begin{lemma}
\label{obs:next}
If $y \leadsto_{w} z$ then $w[x,y] \cdot w[z,v] = w[x,v]$ where $x,y,z,v \in D$.
\end{lemma}
\begin{proof}
Because $y \leadsto_{w} z$ it follows that $w[y+1,z-1] = \varepsilon$. Since we can write $w[x,v]$ as $w[x,y] \cdot w[y+1,z-1] \cdot w[z,v]$ and because $w[y+1,z-1] = \varepsilon$, it follows that $w[x,y] \cdot w[z,v] = w[x,v]$.
\end{proof}

\begin{lemma}
\label{obs:insert}
If $w[x_1,y_1] = w[x_2,y_2]$ and we perform $\ins{\zeta}{u}$ then $w'[x_1,y_1] \neq w'[x_2,y_2]$ if $x_1 < u < y_1$ or $x_2 < u < y_2$.
\end{lemma}
\begin{proof}
If $x_1 < u < y_1$ then it follows that $|w'[x_1,y_1]| = |w[x_1,y_1]| + 1$ but since $w'[x_2,y_2]| = |w[x_2,y_2]|$ it follows that $w'[x_1,y_1] \neq w'[x_2,y_2]$. The reasoning for when $x_2 < u < y_2$ is analogous.

There is the case when $w(u) \neq \varepsilon$ and $x_1 < u < y_1$ or $x_2 < u < y_2$. However since we have the restriction that an update \emph{must} change the word (i.\,e.\xspace we cannot perform $\ins{\zeta}{u}$ if $w(u) = \zeta$), this case is trivial.
\end{proof}

\subsubsection{Actual proof of \cref{lemma:eqsubstr}}
\input{proof-equalsubstr.tex}

\section{Proofs for \cref{sec:main}}
\subsection{Proof of \cref{lemma:next}}
We first observe the following helpful result:
\begin{lemma}\label{obs:nextins}
	Let $\partial = \ins{\zeta}{u}$ and let $x \leadsto_{w} y$ for $x,y \in D$. We have that $x \not\leadsto_{w'} y$ if and only if $x<u<y$.
\end{lemma}
\begin{proof}
	Let $\zeta \in \Sigma$, if we perform the update $\ins{\zeta}{u}$ on $\mathcal{W}$ where $x<u<y$ then it follows that there exists some $z$ such that $w'(z) \neq \varepsilon$ and $x<z<y$. Therefore it cannot be the case that $x \leadsto_{w'} y$, so $x \not\leadsto_{w'} y$.

	If it is not the case that $x<u<y$ then it cannot be that there exists some $z \in D$ such that $x<z<y$ where $w'(z) \neq \varepsilon$. Therefore, if $x \leadsto_{w} y$ and $\partial = \ins{\zeta}{u}$ then $x \not\leadsto_{w'} y$ if and only if $x<u<y$.
\end{proof}
\subsubsection{Actual proof of \cref{lemma:next}}
\input{proof-nextsymbol.tex}

\subsection{Proof of \cref{lemma:eqsubstr}}
We first observe two results which help us in the actual proof of \cref{lemma:eqsubstr}:

\begin{lemma}
\label{obs:next}
If $y \leadsto_{w} z$ then $w[x,y] \cdot w[z,v] = w[x,v]$ where $x,y,z,v \in D$.
\end{lemma}
\begin{proof}
Because $y \leadsto_{w} z$ it follows that $w[y+1,z-1] = \varepsilon$. Since we can write $w[x,v]$ as $w[x,y] \cdot w[y+1,z-1] \cdot w[z,v]$ and because $w[y+1,z-1] = \varepsilon$, it follows that $w[x,y] \cdot w[z,v] = w[x,v]$.
\end{proof}

\begin{lemma}
\label{obs:insert}
If $w[x_1,y_1] = w[x_2,y_2]$ and we perform $\ins{\zeta}{u}$ then $w'[x_1,y_1] \neq w'[x_2,y_2]$ if $x_1 < u < y_1$ or $x_2 < u < y_2$.
\end{lemma}
\begin{proof}
If $x_1 < u < y_1$ then it follows that $|w'[x_1,y_1]| = |w[x_1,y_1]| + 1$ but since $w'[x_2,y_2]| = |w[x_2,y_2]|$ it follows that $w'[x_1,y_1] \neq w'[x_2,y_2]$. The reasoning for when $x_2 < u < y_2$ is analogous.

There is the case when $w(u) \neq \varepsilon$ and $x_1 < u < y_1$ or $x_2 < u < y_2$. However since we have the restriction that an update \emph{must} change the word (i.\,e.\xspace we cannot perform $\ins{\zeta}{u}$ if $w(u) = \zeta$), this case is trivial.
\end{proof}

\subsubsection{Actual proof of \cref{lemma:eqsubstr}}
\input{proof-equalsubstr.tex}

\section{Introduction}\label{sec:intro}
\input{sec-intro}
\section{Preliminaries}\label{sec:prelim}
\input{sec-prelim}
\section{Core Spanners are in \ifmmode{\mathsf{DynCQ}}\else{\textsf{DynCQ}}\xspace\fi}\label{sec:main}
\input{sec-main}
\section{Relations in \ifmmode{\mathsf{SpLog}}\else{\textsf{SpLog}}\xspace\fi and \ifmmode{\mathsf{DynCQ}}\else{\textsf{DynCQ}}\xspace\fi}\label{sec:rel}
\input{sec-rel}
\section{Conclusions}\label{sec:conc}
\input{sec-conc}

\newpage

\subsection{Document Spanners and Spanner Algebra}\label{sec:spanners}

\input{sec-prelim-spanners}

\subsection{Spanner Logic}\label{sec:splog}

\input{sec-prelim-splog}

\subsection{Dynamic complexity}\label{sec:dyn}

\input{sec-prelim-dyn}

\subsubsection{Primitive Spanner Representations}\label{sec:spanner-rep}
Let $w := a_1 \cdot a_2 \cdots a_n$ be a word, where $n \geq 0$ and $a_1,\dots,a_n \in \Sigma$. A \emph{span} of $w$ is an interval $\spn{i,j}$ with $1 \leq i \leq j \leq n+1$ and $i,j \geq 0$. Given a span $\spn{i,j}$ of a word $w$, we define the subword $w_{\spn{i,j}}$ as $a_i \cdot a_{i+1} \cdots a_{j-1}$.
\begin{example}
Consider the word
$w:= \mathtt{banana}$.	As $|w|=6$, the spans of $w$ are the $\spn{i,j}$ with $1\leq i \leq j\leq 7$. For example, we have $w_{\spn{1,2}}=\mathtt{b}$ and $w_{\spn{2,4}}=w_{\spn{4,6}}=\mathtt{an}$. Although both spans describe the same subword \texttt{an}, the two occurrences are at different locations (and, thus, at different spans). Analogously, we have $w_{\spn{1,1}}=w_{\spn{2,2}}=\cdots=w_{\spn{7,7}}=\varepsilon$, but $\spn{i,i}\neq \spn{i',i'}$ for all distinct $1\leq i,i'\leq 7$.
\end{example}

Let  $V \subseteq \Xi$ and  $w \in \Sigma^*$. A $(V,w)$\emph{-tuple} is a function $\mu$ that maps each  $x\in V$ to a span $\mu(x)$ of $w$. A set of $(V,w)$-tuples is called a  $(V,w)$\emph{-relation}. A \emph{spanner} P is a function that maps every $w \in \Sigma^*$ to a $(V,w)$-relation~$P(w)$.
We write $\SVars{P}$ to denote the set of variables $V$ of a spanner~$P$.
Two spanners $P_1$ and $P_2$ are \emph{equivalent} if $\SVars{P_1} = \SVars{P_2}$ and  $P_1(w) = P_2(w)$ holds for all $w \in \Sigma^*$.

In the usual applications of spans and spanners, the word $w$ is some type of text. Hence, we can view a spanner $P$ as mapping an input text $w$ to a $(V,w)$-relation  $P(w)$, which can be understood as a table of spans of $w$.

To define spanners, we use two types of \emph{primitive spanner representations}, the so-called \emph{regex formulas} and \emph{variable-set automata}. Both extend classical mechanisms for regular languages (regular expressions and NFAs, respectively) with variables.
\subparagraph*{Regex formulas:}
The syntax of regex formulas is defined by the following
$\alpha := \emptyset \mid \varepsilon \mid a \mid (\alpha \lor \alpha) \mid (\alpha \cdot \alpha) \mid (\alpha)^* \mid x \{ \alpha \}, $
where $a \in \Sigma$ and $x \in \Xi$. We use $\alpha^+$ to denote $\alpha \cdot \alpha^*$.

Like~\cite{fre:splog}, we define the  semantics of regex formulas using two step-semantics with  \emph{ref-words} (originally introduced by Schmid~\cite{sch:cha} in a different context). A ref-word is a word over the extended alphabet $(\Sigma \cup \Gamma)$ where $\Gamma := \{ \openvar{x}, \closevar{x} \mid x \in \Xi \}$. The symbols $\openvar{x}$ and $\closevar{x}$ represent the beginning and end of the span for the variable $x$.
The first step in the definition of semantics is treating each regex formula $\alpha$ as generators of languages of ref-words $\rlang(\alpha)\subseteq (\Sigma \cup \Gamma)^*$, which  is defined by $\rlang(\emptyset) := \emptyset$, $\rlang(a) := \{ a \}$ where $a \in \Sigma \cup \{ \varepsilon \}$, $\rlang(\alpha_1 \lor \alpha_2) := \rlang(\alpha_1) \cup \rlang(\alpha_2)$, $\rlang(\alpha_1 \cdot \alpha_2) := \rlang(\alpha_1) \cdot \rlang(\alpha_2)$, $\rlang(\alpha^*) := \rlang(\alpha)^*$, and $\rlang(x\{ \alpha \}) := \openvar{x} \rlang(\alpha) \closevar{x}$.

Let $\SVars{\alpha}$ be the set of all $x \in \Xi$ such that $x\{ \}$ occurs somewhere in $\alpha$. A ref-word $r \in \rlang(\alpha)$ is \emph{valid} if for all $x \in \SVars{\alpha}$, we have that $|r|_{\openvar{x}} = 1$.
We denote the set of valid ref-words in $\rlang(\alpha)$ as $\validr{\alpha}$ and say that
a regex formula is \emph{functional} if $\rlang(\alpha) = \validr{\alpha}$.
We write $\mathsf{RGX}$ for the set of all functional regex formulas.
By definition,  for  every $\alpha\in\mathsf{RGX}$, every $r \in \validr{\alpha}$, and  every $x \in \SVars{\alpha}$, there is  a unique factorization $r = r_1 \openvar{x} r_2 \closevar{x} r_3$.

This allows us to define the second step of the semantics, which turns such a  factorization for some variable $x$ into a span $\mu(x)$. To this end, we define a morphism $\mathsf{clr} \colon (\Sigma \cup \Gamma)^* \rightarrow \Sigma^*$ by $\mathsf{clr}(a) := a $ for $a \in \Sigma$ and $\mathsf{clr}(g) = \varepsilon$ for all $g \in \Gamma$.
For a  factorization $r = r_1 \openvar{x} r_2 \closevar{x} r_3$, $\mathsf{clr}(r_1)$ is the substring of $w$ that appears before $\mu(x)$ and $\mathsf{clr}(r_2)$ is the substring $w_{\mu(x)}$.

We use this for the definition of the semantics as follows:
For $\alpha \in \mathsf{RGX}$ and $w \in \Sigma^*$, let $V := \SVars{\alpha}$ and (more importantly) $\validr{\alpha, w} := \{ r \in \validr{\alpha} \mid \mathsf{clr}(r)=w \}$.

Every $r \in \validr{\alpha,w}$ defines a $(V,w)$-tuple $\mu^r$ in the following way: For every $x \in \SVars{\alpha}$, we use  the unique factorization $r = r_1 \openvar{x} r_2 \closevar{x} r_3$ to define $\mu^r(x) := \spn{|\mathsf{clr}(r_1)|+1, |\mathsf{clr}(r_1 r_2)|+1	}$.
The spanner $\spanner{\alpha}$ is then defined by $\spanner{\alpha}(w) := \{ \mu^r \mid r \in \validr{\alpha,w} \} $ for all $w\in\Sigma^*$.

\subparagraph*{Variable-set automata:} Variable-set automata (short: \emph{vset-automata}) are NFAs that may use variable operations $\openvar{x}$ and $\closevar{x}$ as  transitions. More formally, let  $V \subset \Xi$ be a finite set of variables.
 A variable-set automaton over $\Sigma$ with variables $V$ is a tuple $A = (Q, q_0, q_f , \delta)$, where $Q$ is the set of states, $q_0 \in Q$ is the initial state, $q_f \in Q$ is the accepting state, and $\delta \colon Q \times (\Sigma \cup \{ \varepsilon \} \cup \Gamma_V) \rightarrow \powerset{Q}$ is the transition function with $\Gamma_V := \{ \openvar{x}, \closevar{x} \mid x \in V \}$.

We define the semantics using a two-step approach analogous to the semantic definition of regex formulas.
 Firstly, we treat $A$ as an NFA that defines the ref-language defined by $\rlang(A):=\{ r \in (\Sigma \cup \Gamma_V)^* \mid q_f \in \delta^*(q_0, r) \}$, where
 the function $\delta^* \colon Q \times (\Sigma \cup \Gamma_V) \rightarrow \powerset{Q}$ is defined such that for all $p,q \in Q$ and $r \in (\Sigma \cup \Gamma_V)^*$, $q \in \delta^*(p,r)$ if and only if there exists a path in $A$ from $p$ to $q$ with the label $r$.

Secondly, let $\SVars{A}$ be the set of $x \in V$ such that $\openvar{x}$ or $\closevar{x}$ appears in $A$. A ref-word $r \in \rlang(A)$ is \emph{valid} if for every $x \in \SVars{A}$, $|r|_{\openvar{x}} = |r|_{\closevar{x}}=1$, and $\openvar{x}$ always occurs to the left of $\closevar{x}$. Then $\validr{A}$, $\validr{A,w}$ and $\spanner{A}$ are defined analogously to regex formulas. We denote the set of all vset-automata using $\mathsf{VA_{set}}$. As for regex formulas, a vset-automaton $A\in\mathsf{VA_{set}}$ is called \emph{functional} if $\rlang(A)=\validr{A}$.

\begin{example}\label{ex:regexAutomaton}
We define the functional regex formula
$\alpha:=\Sigma^*\cdot x\{(\mathtt{wine})\lor(\mathtt{cake})\}\cdot\Sigma^*$. We also define the functional vset-automaton~$A$ as follows:
\begin{center}
	\begin{tikzpicture}[on grid, node distance =12mm,every loop/.style={shorten >=0pt}, every state/.style={inner sep=0pt,minimum size=5mm}]
	\node[state,initial text=,initial by arrow] (q0) {};
	\node[state, right= of q0] (q1) {};
	\node[state, above right=of q1] (b1) {};
	\node[state, right=of b1] (b2) {};
	\node[state, right=of b2] (b3) {};

	\node[state, below right=of q1] (c1) {};
		\node[state, right=of c1] (c2) {};
		\node[state, right=of c2] (c3) {};
	\node[state, below right=of b3] (q3) {};
	\node[state,accepting,right=of q3] (q4) {};	\path[->]
	(q0) edge [loop above] node {$\Sigma$} (q0)
	(q0) edge node[above] {$\openvar{x}$} (q1)
	(q1) edge[pos=0.2] node[above] {$\mathtt{w}$} (b1)
	(b1) edge[] node[above] {$\mathtt{i}$} (b2)
	(b2) edge[] node[above] {$\mathtt{n}$} (b3)
	(b3) edge[] node[above] {$\mathtt{e}$} (q3)
	(q1) edge[pos=0.2] node[below] {$\mathtt{c}$} (c1)
(c1) edge[] node[below] {$\mathtt{a}$} (c2)
(c2) edge[] node[below] {$\mathtt{k}$} (c3)
(c3) edge[] node[below] {$\mathtt{e}$} (q3)
	(q3) edge node[above] {$\closevar{x}$} (q4)
(q4) edge [loop above] node {$\Sigma$} (q4)
	;
	\end{tikzpicture}
\end{center}
For all $w\in\Sigma^*$, we have that $\spanner{\alpha}(w)=\spanner{A}(w)$ contains exactly those $(\{x\},w)$-tuples $\mu$ that have $w_{\mu(x)}=\mathtt{wine}$ or $w_{\mu(x)}=\mathtt{cake}$.
\end{example}

\subsubsection{Spanner Algebra}\label{sec:spannerAlgebra}
We now introduce an algebra on spanners in order to construct more complex spanners.

\begin{definition}
Two spanners $P_1$ and $P_2$ are \emph{compatible} if $\SVars{P_1}=\SVars{P_2}$.
We define  the following algebraic operators for all spanners $P, P_1, P_2$:
\begin{itemize}
	\item If $P_1$ and $P_2$ are compatible, their \emph{union} $(P_1 \cup P_2)$ and their \emph{difference} $(P_1\setminus P_2)$ are defined by $(P_1 \cup P_2)(w) := P_1(w) \cup P_2(w)$ and $(P_1 \setminus P_2)(w) := P_1(w) \setminus P_2(w)$.
	\item The \emph{projection} $\pi_Y P$ for $Y \subseteq \SVars{P}$ is defined by $\pi_Y P(w) := P|_Y(w)$, where $P|_Y(w)$ is the restriction of all $\mu \in P(w)$ to~$Y$.
	\item The \emph{natural join} $P_1 \bowtie P_2$ is obtained by defining each $(P_1 \bowtie P_2)(w)$ as the set of all  $(V_1 \cup V_2,w)$-tuples $\mu$ for which there exists $\mu_1 \in P_1(w)$ and $\mu_2 \in P_2(w)$ with $\mu|_{V_1}(w) = \mu_1(w)$ and $\mu|_{V_2}(w) = \mu_2(w)$, where $V_i := \SVars{P_i}$ for $i \in \{ 1,2 \}$.
	\item For every  $k$-ary relation $R \subseteq (\Sigma^*)^k$ and variables $x_1, \dots, x_k \in \SVars{P}$, the \emph{selection}  $\upxi^R_{x_1 \dots x_k}P$ is defined by
	$\upxi^R_{x_1 \dots x_k} P(w):= \{\mu \in P(w) \mid (w_{\mu(x_1)} , \dots , w_{\mu(x_k)}) \in R\}$ for $w\in\Sigma^*$.
\end{itemize}
Let  $\SVars{P_1 \cup P_2} := \SVars{P_1\setminus P_2}:=\SVars{P_1}=\SVars{P_2}$,   $\SVars{\pi_Y P} := Y$,  $\SVars{P_1 \bowtie P_2} := \SVars{P_1} \cup \SVars{P_2}$, and $\SVars{\upxi^R_{x_1 \dots x_k}} := \SVars{P}$.
\end{definition}

 Note that the relations $R$ in the selection are usually infinite; and they are never considered part of the input.

Let $O$ be a spanner algebra and let $C$ be a class of primitive spanner representations, then we use $C^O$ to denote the set of all spanner representations that can be constructed by repeated combinations of the symbols for the operators from $O$ with the spanner representation from~$C$. We denote the closure of $\spanner{C}$ under the spanner operators $O$ as $\spanner{C^O}$.
\begin{example}

Let $\alpha_1:= \Sigma^*x\{\Sigma^*\}\Sigma^*y\{\Sigma^*\}\Sigma^*$ and $\alpha_2:=\Sigma^*\cdot x\{(\mathtt{wine})\lor(\mathtt{cake})\}\cdot\Sigma^*$ (recall Example~\ref{ex:regexAutomaton}). We combine the two regex formulas into a core spanner $P := \pi_{x}\upxi^=_{x,y} (\alpha_1\bowtie\alpha_2)$. Then $\spanner{P}(w)$ contains all $(\{x\},w)$-tuples $\mu$ such that $w_{\mu(x)}$ is an occurrence of \texttt{wine} or \texttt{cake} in $w$ that is followed by another occurrence of the same word.
\end{example}

Like  Fagin et al. \cite{fag:spa}, we are mostly concerned with string equality selections $\upxi^=$. Following~$\cite{fag:spa,pet:rec}$, we focus on the class  of \emph{regular spanners} $\spanner{\rgx^{\spanreg}}$, the class of  \emph{core spanners}\footnote{As this class captures the core functionality of SystemT.}  $\spanner{\rgx^{\core}}$
and the class of \emph{generalized core spanners}  $\spanner{\rgx^{\cored}}$, where
$\mathsf{reg}:=\{\pi,\cup,\bowtie\}$ and  $\mathsf{core} := \{ \pi, \upxi^=, \cup, \bowtie\}$.
As shown in~\cite{fag:spa}, we have
\[ \spanner{\rgx^{\spanreg}}=\spanner{\mathsf{VA}_{\mathsf{set}}^{\spanreg}} =\spanner{\mathsf{VA_{set}}}  \subset  \spanner{\rgx^{\core}}=\spanner{\mathsf{VA}_{\mathsf{set}}^{\core}}\subset \spanner{\rgx^{\cored}}=\spanner{\mathsf{VA}_{\mathsf{set}}^{\cored}}. \]
In other words, there is a proper hierarchy of regular, core, and generalized core spanners; and for each of the classes, we can choose regex formulas or vset-automata as primitive spanner representations. As shown in~\cite{fre:splog}, functional vset-automata have the same expressive power as vset-automata in general. The size difference can be exponential, but this does not matter for the purpose of the present paper.

\section{Introduction}\label{sec:intro}
\input{sec-intro}
\section{Preliminaries}\label{sec:prelim}
\input{sec-prelim}
\section{Core Spanners are in \ifmmode{\mathsf{DynCQ}}\else{\textsf{DynCQ}}\xspace\fi}\label{sec:main}
\input{sec-main}
\section{Relations in \ifmmode{\mathsf{SpLog}}\else{\textsf{SpLog}}\xspace\fi and \ifmmode{\mathsf{DynCQ}}\else{\textsf{DynCQ}}\xspace\fi}\label{sec:rel}
\input{sec-rel}
\section{Conclusions}\label{sec:conc}
\input{sec-conc}

\newpage

\subsubsection{Primitive Spanner Representations}\label{sec:spanner-rep}
Let $w := a_1 \cdot a_2 \cdots a_n$ be a word, where $n \geq 0$ and $a_1,\dots,a_n \in \Sigma$. A \emph{span} of $w$ is an interval $\spn{i,j}$ with $1 \leq i \leq j \leq n+1$ and $i,j \geq 0$. Given a span $\spn{i,j}$ of a word $w$, we define the subword $w_{\spn{i,j}}$ as $a_i \cdot a_{i+1} \cdots a_{j-1}$.
\begin{example}
Consider the word
$w:= \mathtt{banana}$.	As $|w|=6$, the spans of $w$ are the $\spn{i,j}$ with $1\leq i \leq j\leq 7$. For example, we have $w_{\spn{1,2}}=\mathtt{b}$ and $w_{\spn{2,4}}=w_{\spn{4,6}}=\mathtt{an}$. Although both spans describe the same subword \texttt{an}, the two occurrences are at different locations (and, thus, at different spans). Analogously, we have $w_{\spn{1,1}}=w_{\spn{2,2}}=\cdots=w_{\spn{7,7}}=\varepsilon$, but $\spn{i,i}\neq \spn{i',i'}$ for all distinct $1\leq i,i'\leq 7$.
\end{example}

Let  $V \subseteq \Xi$ and  $w \in \Sigma^*$. A $(V,w)$\emph{-tuple} is a function $\mu$ that maps each  $x\in V$ to a span $\mu(x)$ of $w$. A set of $(V,w)$-tuples is called a  $(V,w)$\emph{-relation}. A \emph{spanner} P is a function that maps every $w \in \Sigma^*$ to a $(V,w)$-relation~$P(w)$.
We write $\SVars{P}$ to denote the set of variables $V$ of a spanner~$P$.
Two spanners $P_1$ and $P_2$ are \emph{equivalent} if $\SVars{P_1} = \SVars{P_2}$ and  $P_1(w) = P_2(w)$ holds for all $w \in \Sigma^*$.

In the usual applications of spans and spanners, the word $w$ is some type of text. Hence, we can view a spanner $P$ as mapping an input text $w$ to a $(V,w)$-relation  $P(w)$, which can be understood as a table of spans of $w$.

To define spanners, we use two types of \emph{primitive spanner representations}, the so-called \emph{regex formulas} and \emph{variable-set automata}. Both extend classical mechanisms for regular languages (regular expressions and NFAs, respectively) with variables.
\subparagraph*{Regex formulas:}
The syntax of regex formulas is defined by the following
$\alpha := \emptyset \mid \varepsilon \mid a \mid (\alpha \lor \alpha) \mid (\alpha \cdot \alpha) \mid (\alpha)^* \mid x \{ \alpha \}, $
where $a \in \Sigma$ and $x \in \Xi$. We use $\alpha^+$ to denote $\alpha \cdot \alpha^*$.

Like~\cite{fre:splog}, we define the  semantics of regex formulas using two step-semantics with  \emph{ref-words} (originally introduced by Schmid~\cite{sch:cha} in a different context). A ref-word is a word over the extended alphabet $(\Sigma \cup \Gamma)$ where $\Gamma := \{ \openvar{x}, \closevar{x} \mid x \in \Xi \}$. The symbols $\openvar{x}$ and $\closevar{x}$ represent the beginning and end of the span for the variable $x$.
The first step in the definition of semantics is treating each regex formula $\alpha$ as generators of languages of ref-words $\rlang(\alpha)\subseteq (\Sigma \cup \Gamma)^*$, which  is defined by $\rlang(\emptyset) := \emptyset$, $\rlang(a) := \{ a \}$ where $a \in \Sigma \cup \{ \varepsilon \}$, $\rlang(\alpha_1 \lor \alpha_2) := \rlang(\alpha_1) \cup \rlang(\alpha_2)$, $\rlang(\alpha_1 \cdot \alpha_2) := \rlang(\alpha_1) \cdot \rlang(\alpha_2)$, $\rlang(\alpha^*) := \rlang(\alpha)^*$, and $\rlang(x\{ \alpha \}) := \openvar{x} \rlang(\alpha) \closevar{x}$.

Let $\SVars{\alpha}$ be the set of all $x \in \Xi$ such that $x\{ \}$ occurs somewhere in $\alpha$. A ref-word $r \in \rlang(\alpha)$ is \emph{valid} if for all $x \in \SVars{\alpha}$, we have that $|r|_{\openvar{x}} = 1$.
We denote the set of valid ref-words in $\rlang(\alpha)$ as $\validr{\alpha}$ and say that
a regex formula is \emph{functional} if $\rlang(\alpha) = \validr{\alpha}$.
We write $\mathsf{RGX}$ for the set of all functional regex formulas.
By definition,  for  every $\alpha\in\mathsf{RGX}$, every $r \in \validr{\alpha}$, and  every $x \in \SVars{\alpha}$, there is  a unique factorization $r = r_1 \openvar{x} r_2 \closevar{x} r_3$.

This allows us to define the second step of the semantics, which turns such a  factorization for some variable $x$ into a span $\mu(x)$. To this end, we define a morphism $\mathsf{clr} \colon (\Sigma \cup \Gamma)^* \rightarrow \Sigma^*$ by $\mathsf{clr}(a) := a $ for $a \in \Sigma$ and $\mathsf{clr}(g) = \varepsilon$ for all $g \in \Gamma$.
For a  factorization $r = r_1 \openvar{x} r_2 \closevar{x} r_3$, $\mathsf{clr}(r_1)$ is the substring of $w$ that appears before $\mu(x)$ and $\mathsf{clr}(r_2)$ is the substring $w_{\mu(x)}$.

We use this for the definition of the semantics as follows:
For $\alpha \in \mathsf{RGX}$ and $w \in \Sigma^*$, let $V := \SVars{\alpha}$ and (more importantly) $\validr{\alpha, w} := \{ r \in \validr{\alpha} \mid \mathsf{clr}(r)=w \}$.

Every $r \in \validr{\alpha,w}$ defines a $(V,w)$-tuple $\mu^r$ in the following way: For every $x \in \SVars{\alpha}$, we use  the unique factorization $r = r_1 \openvar{x} r_2 \closevar{x} r_3$ to define $\mu^r(x) := \spn{|\mathsf{clr}(r_1)|+1, |\mathsf{clr}(r_1 r_2)|+1	}$.
The spanner $\spanner{\alpha}$ is then defined by $\spanner{\alpha}(w) := \{ \mu^r \mid r \in \validr{\alpha,w} \} $ for all $w\in\Sigma^*$.

\subparagraph*{Variable-set automata:} Variable-set automata (short: \emph{vset-automata}) are NFAs that may use variable operations $\openvar{x}$ and $\closevar{x}$ as  transitions. More formally, let  $V \subset \Xi$ be a finite set of variables.
 A variable-set automaton over $\Sigma$ with variables $V$ is a tuple $A = (Q, q_0, q_f , \delta)$, where $Q$ is the set of states, $q_0 \in Q$ is the initial state, $q_f \in Q$ is the accepting state, and $\delta \colon Q \times (\Sigma \cup \{ \varepsilon \} \cup \Gamma_V) \rightarrow \powerset{Q}$ is the transition function with $\Gamma_V := \{ \openvar{x}, \closevar{x} \mid x \in V \}$.

We define the semantics using a two-step approach analogous to the semantic definition of regex formulas.
 Firstly, we treat $A$ as an NFA that defines the ref-language defined by $\rlang(A):=\{ r \in (\Sigma \cup \Gamma_V)^* \mid q_f \in \delta^*(q_0, r) \}$, where
 the function $\delta^* \colon Q \times (\Sigma \cup \Gamma_V) \rightarrow \powerset{Q}$ is defined such that for all $p,q \in Q$ and $r \in (\Sigma \cup \Gamma_V)^*$, $q \in \delta^*(p,r)$ if and only if there exists a path in $A$ from $p$ to $q$ with the label $r$.

Secondly, let $\SVars{A}$ be the set of $x \in V$ such that $\openvar{x}$ or $\closevar{x}$ appears in $A$. A ref-word $r \in \rlang(A)$ is \emph{valid} if for every $x \in \SVars{A}$, $|r|_{\openvar{x}} = |r|_{\closevar{x}}=1$, and $\openvar{x}$ always occurs to the left of $\closevar{x}$. Then $\validr{A}$, $\validr{A,w}$ and $\spanner{A}$ are defined analogously to regex formulas. We denote the set of all vset-automata using $\mathsf{VA_{set}}$. As for regex formulas, a vset-automaton $A\in\mathsf{VA_{set}}$ is called \emph{functional} if $\rlang(A)=\validr{A}$.

\begin{example}\label{ex:regexAutomaton}
We define the functional regex formula
$\alpha:=\Sigma^*\cdot x\{(\mathtt{wine})\lor(\mathtt{cake})\}\cdot\Sigma^*$. We also define the functional vset-automaton~$A$ as follows:
\begin{center}
	\begin{tikzpicture}[on grid, node distance =12mm,every loop/.style={shorten >=0pt}, every state/.style={inner sep=0pt,minimum size=5mm}]
	\node[state,initial text=,initial by arrow] (q0) {};
	\node[state, right= of q0] (q1) {};
	\node[state, above right=of q1] (b1) {};
	\node[state, right=of b1] (b2) {};
	\node[state, right=of b2] (b3) {};

	\node[state, below right=of q1] (c1) {};
		\node[state, right=of c1] (c2) {};
		\node[state, right=of c2] (c3) {};
	\node[state, below right=of b3] (q3) {};
	\node[state,accepting,right=of q3] (q4) {};	\path[->]
	(q0) edge [loop above] node {$\Sigma$} (q0)
	(q0) edge node[above] {$\openvar{x}$} (q1)
	(q1) edge[pos=0.2] node[above] {$\mathtt{w}$} (b1)
	(b1) edge[] node[above] {$\mathtt{i}$} (b2)
	(b2) edge[] node[above] {$\mathtt{n}$} (b3)
	(b3) edge[] node[above] {$\mathtt{e}$} (q3)
	(q1) edge[pos=0.2] node[below] {$\mathtt{c}$} (c1)
(c1) edge[] node[below] {$\mathtt{a}$} (c2)
(c2) edge[] node[below] {$\mathtt{k}$} (c3)
(c3) edge[] node[below] {$\mathtt{e}$} (q3)
	(q3) edge node[above] {$\closevar{x}$} (q4)
(q4) edge [loop above] node {$\Sigma$} (q4)
	;
	\end{tikzpicture}
\end{center}
For all $w\in\Sigma^*$, we have that $\spanner{\alpha}(w)=\spanner{A}(w)$ contains exactly those $(\{x\},w)$-tuples $\mu$ that have $w_{\mu(x)}=\mathtt{wine}$ or $w_{\mu(x)}=\mathtt{cake}$.
\end{example}

\subsubsection{Spanner Algebra}\label{sec:spannerAlgebra}
We now introduce an algebra on spanners in order to construct more complex spanners.

\begin{definition}
Two spanners $P_1$ and $P_2$ are \emph{compatible} if $\SVars{P_1}=\SVars{P_2}$.
We define  the following algebraic operators for all spanners $P, P_1, P_2$:
\begin{itemize}
	\item If $P_1$ and $P_2$ are compatible, their \emph{union} $(P_1 \cup P_2)$ and their \emph{difference} $(P_1\setminus P_2)$ are defined by $(P_1 \cup P_2)(w) := P_1(w) \cup P_2(w)$ and $(P_1 \setminus P_2)(w) := P_1(w) \setminus P_2(w)$.
	\item The \emph{projection} $\pi_Y P$ for $Y \subseteq \SVars{P}$ is defined by $\pi_Y P(w) := P|_Y(w)$, where $P|_Y(w)$ is the restriction of all $\mu \in P(w)$ to~$Y$.
	\item The \emph{natural join} $P_1 \bowtie P_2$ is obtained by defining each $(P_1 \bowtie P_2)(w)$ as the set of all  $(V_1 \cup V_2,w)$-tuples $\mu$ for which there exists $\mu_1 \in P_1(w)$ and $\mu_2 \in P_2(w)$ with $\mu|_{V_1}(w) = \mu_1(w)$ and $\mu|_{V_2}(w) = \mu_2(w)$, where $V_i := \SVars{P_i}$ for $i \in \{ 1,2 \}$.
	\item For every  $k$-ary relation $R \subseteq (\Sigma^*)^k$ and variables $x_1, \dots, x_k \in \SVars{P}$, the \emph{selection}  $\upxi^R_{x_1 \dots x_k}P$ is defined by
	$\upxi^R_{x_1 \dots x_k} P(w):= \{\mu \in P(w) \mid (w_{\mu(x_1)} , \dots , w_{\mu(x_k)}) \in R\}$ for $w\in\Sigma^*$.
\end{itemize}
Let  $\SVars{P_1 \cup P_2} := \SVars{P_1\setminus P_2}:=\SVars{P_1}=\SVars{P_2}$,   $\SVars{\pi_Y P} := Y$,  $\SVars{P_1 \bowtie P_2} := \SVars{P_1} \cup \SVars{P_2}$, and $\SVars{\upxi^R_{x_1 \dots x_k}} := \SVars{P}$.
\end{definition}

 Note that the relations $R$ in the selection are usually infinite; and they are never considered part of the input.

Let $O$ be a spanner algebra and let $C$ be a class of primitive spanner representations, then we use $C^O$ to denote the set of all spanner representations that can be constructed by repeated combinations of the symbols for the operators from $O$ with the spanner representation from~$C$. We denote the closure of $\spanner{C}$ under the spanner operators $O$ as $\spanner{C^O}$.
\begin{example}

Let $\alpha_1:= \Sigma^*x\{\Sigma^*\}\Sigma^*y\{\Sigma^*\}\Sigma^*$ and $\alpha_2:=\Sigma^*\cdot x\{(\mathtt{wine})\lor(\mathtt{cake})\}\cdot\Sigma^*$ (recall Example~\ref{ex:regexAutomaton}). We combine the two regex formulas into a core spanner $P := \pi_{x}\upxi^=_{x,y} (\alpha_1\bowtie\alpha_2)$. Then $\spanner{P}(w)$ contains all $(\{x\},w)$-tuples $\mu$ such that $w_{\mu(x)}$ is an occurrence of \texttt{wine} or \texttt{cake} in $w$ that is followed by another occurrence of the same word.
\end{example}

Like  Fagin et al. \cite{fag:spa}, we are mostly concerned with string equality selections $\upxi^=$. Following~$\cite{fag:spa,pet:rec}$, we focus on the class  of \emph{regular spanners} $\spanner{\rgx^{\spanreg}}$, the class of  \emph{core spanners}\footnote{As this class captures the core functionality of SystemT.}  $\spanner{\rgx^{\core}}$
and the class of \emph{generalized core spanners}  $\spanner{\rgx^{\cored}}$, where
$\mathsf{reg}:=\{\pi,\cup,\bowtie\}$ and  $\mathsf{core} := \{ \pi, \upxi^=, \cup, \bowtie\}$.
As shown in~\cite{fag:spa}, we have
\[ \spanner{\rgx^{\spanreg}}=\spanner{\mathsf{VA}_{\mathsf{set}}^{\spanreg}} =\spanner{\mathsf{VA_{set}}}  \subset  \spanner{\rgx^{\core}}=\spanner{\mathsf{VA}_{\mathsf{set}}^{\core}}\subset \spanner{\rgx^{\cored}}=\spanner{\mathsf{VA}_{\mathsf{set}}^{\cored}}. \]
In other words, there is a proper hierarchy of regular, core, and generalized core spanners; and for each of the classes, we can choose regex formulas or vset-automata as primitive spanner representations. As shown in~\cite{fre:splog}, functional vset-automata have the same expressive power as vset-automata in general. The size difference can be exponential, but this does not matter for the purpose of the present paper.

\subsection{Document Spanners and Spanner Algebra}\label{sec:spanners}

\input{sec-prelim-spanners}

\subsection{Spanner Logic}\label{sec:splog}

\input{sec-prelim-splog}

\subsection{Dynamic complexity}\label{sec:dyn}

\input{sec-prelim-dyn}


\section{Introduction}
Predicting possible future trajectories of objects in traffic scenes, such as cars and pedestrians, plays an essential role in anticipatory driving.
Only by having knowledge about the type of object and its possible movement patterns, we are able to make safe decisions as a human driver.
Having predictions as an additional input to a driver assistance system or an autonomous driving system would be beneficial to its internal decision-making process.
Such a system could make faster and possibly more informed decisions regarding the control of the vehicle, which leads to an increase in safety.

Predicting the future frames of videos of street scenes is one way to anticipate the movement of objects.
However, to support a system such as an autonomously driving car, the quality of the predicted frames must be high enough to enable the reliable detection of relevant objects.
Depending on the identified object, the decision process will vary greatly.
State-of-the-art object detection software produces good results on real videos of street scenes.
Thus, if a prediction looks as similar to the real data as possible, we can assume that detecting objects correctly will be easier.
\begin{figure}[t]
	\centering
	\vspace*{2mm}
	\includegraphics[width=.9\linewidth]{IntroFig.pdf}
	\vspace*{-1mm}
	\caption{Example predictions of the different prediction-enhancement pipelines. a: Input Sequence, b: FutureGAN \cite{Aigner2018}, c: DeblurGAN \cite{Kopyn2018} (transposed convolutions), d: DeblurGAN (NN-upsampling + convolution), e: SRGAN \cite{Ledig2016}.}
	\label{intro-example}
	\vspace*{-4mm}
\end{figure}

Due to the success of neural networks on a variety of computer vision tasks, we test the capabilities of neural network-based methods for generating enhanced video predictions that allow for the accurate detection of objects.
Particularly, we build on our previous video prediction network, \emph{FutureGAN} \cite{Aigner2018}, and predict five future frames of a street scene based on five input frames.
The original results on the \emph{Cityscapes} dataset \cite{cordts2016} suggest that the network has learned reasonably good movement representations.
However, for complex input data, such as natural street scenes, the predicted frames suffer from blurring effects and other unrealistic artifacts.
Therefore, we test several additional methods to enhance the predicted frames, thus making them appear more realistic, see figure \ref{intro-example} for example predictions.
For enhancing, we utilize \emph{generative adversarial networks (GANs)} \cite{goodfellow2014}.
In order to make the predictions more realistic and increase object detection results, we test two different GAN-based methods.
The first one is an image super-resolution approach, the \emph{SRGAN} \cite{Ledig2016}, and the second one is a blind motion deblurring approach, the \emph{DeblurGAN} \cite{Kopyn2018}.
In both cases, the frame enhancement is treated as an \emph{image-to-image translation} problem, where GANs have led to good results.

In this paper, we provide a reliable pipeline for predicting traffic scenes.
To prove the effectiveness of our prediction-enhancement pipeline, we evaluate all resulting predictions using the state-of-the-art object detection network \emph{YOLOv3} \cite{redmon2018}.
Our final model is able to produce predictions of both good visual quality and high detection accuracy.
The \emph{average precision (AP)} values for the object class "car" can be increased by about 9\% for each prediction step, compared to the non-enhanced predictions.

\section{Related Work}
Ranzato \etal \cite{Ranzato2014} first introduced a baseline for video prediction using deep neural networks.
Since then, the deep learning-based prediction of future traffic sequences has become a widely researched topic in computer vision, especially in the autonomous driving community.

Due to the uncertainty in predicting the future, generating high-quality predictions of natural traffic scenes is a very complex task.
This is why some approaches simplify this task and focus on predicting semantic segmentation masks, rather than generating the pixel values of the frames
\cite{Luc2017,Jin2017,Jin2017b,Nabavi2018,Bhattacharyya2019}.
Many of these approaches, as well as approaches that directly generate the pixel values, use recurrent neural network structures \cite{DeBrabandere2016,Lotter2017,Elsayed2018,Wei2018,Kosiorek2018,Byeon2018,Nabavi2018,Xu2018}.
Lotter \etal \cite{Lotter2017}, for example, utilized long short-term memory (LSTM) \cite{Hochreiter1997} units to generate the pixel values of the frame one time step ahead.
Bhattacharjee \etal \cite{Bhattacharjee2017} generate predictions using a multi-stage GAN that takes input frames at different scales.
Using GANs \cite{Bhattacharjee2018,Aigner2018,Bhattacharjee2017}, or a combination of GANs and recurrent modules \cite{Liang2017}, are further common methods to predict video frames of traffic scenes.

Despite the recent advances in this field, the resulting frames often lack realism.
To make predictions occur more realistic, others tackled the problem by learning separate representations for the static and dynamic components of a video.
This is done either by incorporating motion conditions, such as optical flow information \cite{Gao2018,Reda2018,Hao2018,Jin2017,Liang2017}, or by learning sparse features that represent pixel dynamics \cite{Liu2018}.
Decomposing the video into static and non-static components allows the network to simply reproduce the values of the static part for the majority of pixels.
Transformations are then only performed on the non-static pixels.
This leads to the problem of occluded and new objects not being properly modeled, especially in long-term predictions.

Our approach builds on the idea of enhancing each prediction directly using a second network.
Recently, related ideas without an application for traffic scenes were introduced \cite{Zhao2018,Xiong2018}.
These approaches use two-stage networks to first generate subsequent frames from structure and content conditions, and then refine the frames using temporal signals or motion dynamics.
We, on the other hand, use the learned motion representations of a GAN-based model to predict a set of future frames from a set of input frames.
We then use a separate second model, an image-to-image translation GAN, to eliminate the artifacts and blurring effects caused by the transformations of the first network.

\section{Enhancement of Predicted Video Frames}
The methods used in this paper are based on GANs.
In an adversarial setting, a generator network is trained to model the data distribution of the training data.
During training, a second network, the discriminator, provides feedback to the generator about the similarity between the modeled and the observed data distribution.
This results in a minimax game.
The discriminator $D$ tries to maximize its score of correctly classifying the samples it observes as real or fake.
The generator $G$ tries to fool the discriminator by minimizing the difference of the modeled and the data distribution, \ie by optimizing
\begin{equation}
\min_G \max_D \underset{x \sim \mathbb{P}_r}{\mathbb{E}} [\log (D(x))] + \underset{\tilde{x} \sim \mathbb{P}_g}{\mathbb{E}} [\log (1-D(\tilde{x}))] \; ,
\end{equation}
where $\mathbb{P}_r$ is the data distribution, $\mathbb{P}_g$ is the model distribution, implicitly defined by $\tilde{x} = G(z)$, and $z$ is the input sampled from a random distribution $P(z)$.
During training, this approach gradually enforces the generator to produce samples that appear more and more similar to the training data.

However, there are problems with GAN-based approaches.
First, they are hard to train and the highly unstable training process often leads to non-convergence.
Secondly, there is the mode collapse effect.
This means, the generator learns to fool the discriminator by producing samples of a limited set of modes, thus produces samples that lack diversity.
The generator fails to sufficiently model the variation in the real data distribution.

For generating the traffic scene predictions we make use of our recent GAN-based approach, FutureGAN, that avoids these problems.
We then evaluate how the predictions can be enhanced in order to improve the object detection results on the predicted frames.
The methods to enhance the predictions are all based on variants of the \emph{conditional GAN (cGAN)} \cite{mirza2014}, where enhancing is treated as an image-to-image translation problem.
In the following, we describe the approaches used in this paper in more detail.

\subsection{FutureGAN}
To predict the future frames of the traffic sequences, we use FutureGAN.
This network predicts multiple output frames from a set of input frames.
It is trained using the \emph{progressively growing of GANs} technique, introduced by
Karras \etal \cite{karras2018}.
During training, layers are added progressively to both the generator and the discriminator network to increase the frame resolution gradually.
Many architectures were particularly designed to overcome the GAN-related training issues, such as non-convergence and mode collapse \cite{Radford2016, Arjovsky2017b}.
The progressive growing training strategy helps to further improve the GAN training.
Additionally, the authors used feature normalization and a \emph{Wasserstein GAN with gradient penalty (WGAN-GP)} \cite{gulrajani2017} loss to increase the training stability of the network.
For details on the network structure and architectural design, we refer the reader to the original paper \cite{Aigner2018}.

\subsection{DeblurGAN}
\label{sec:deblurgan}
As a first enhancement method, we chose DeblurGAN \cite{Kopyn2018}.
DeblurGAN is a blind motion deblurring method based on cGANs.
The DeblurGAN framework treats motion deblurring as an image-to-image translation problem.
Rather than to estimate a motion kernel, the network is trained to directly translate the image from a blurry version to an unblurred one.

The DeblurGAN loss function
\begin{equation}
\label{eq:dgloss}
\mathcal{L} = \mathcal{L}_\text{GAN} + \lambda \mathcal{L}_\text{X}
\end{equation}
consists of two components,
a WGAN-GP loss term $\mathcal{L}_\text{GAN}$ and a content loss term $\mathcal{L}_\text{X}$,
with $\lambda$ as a balancing factor.
The content loss was introduced in addition to the adversarial loss term to increase the perceptual quality of the generated images.
In contrast to the standard $L_1$ \emph{(MAE)} or $L_2$ \emph{(MSE)} losses, which are based on the differences of the raw pixel values, this \emph{perceptual loss} \cite{Johnson2016} is based on the differences in feature space.
In particular,
\begin{equation}
\label{dgcontentloss}
\mathcal{L}_X = \frac{1}{W_{i,j} H_{i,j}} \displaystyle\sum_{x=1}^{W_{i,j}} \displaystyle\sum_{y=1}^{H_{i,j}} (\phi_{i,j}(I^S)_{x,y} - \phi_{i,j}(G_{\theta}(I^B))_{x,y})^2
\end{equation}
is the $L_2$ difference between the feature maps of the ground truth and the deblurred image of a specific layer in the VGG-19 \cite{simonyan2014} network,
where $\phi_{i,j}$ is the feature map obtained before the $i$-th max-pooling layer and after the $j$-th convolutional layer of the VGG-19 network trained on ImageNet \cite{deng2009}, and $I^S$ and $I^B$ are the sharp ground truth and the blurry predicted frame.
$W_{i,j}$ and $H_{i,j}$ are the width and height dimensions of the feature maps, respectively.
In this case, we used the $VGG_{3,3}$ convolutional layer, since the general image content is typically captured in the lower layers of such a network \cite{zeiler2014}.

The original results of Kopyn \etal \cite{Kopyn2018} show that motion blur and artifacts similar to those of the FutureGAN street scene predictions can be removed effectively.
After training DeblurGAN on our data, we observed that the network generates a checkerboard pattern on the deblurred test images (\cf Figure \ref{dg_structure}).
Following the findings by Odena \etal \cite{odena2016}, we assume these patterns to be caused by the transposed convolutional layers in the upsampling part of the generator network.
Transposed convolutions can produce this type of pattern because of the overlap that occurs when the kernel sizes are not divisible by the strides.
To avoid such undesired patterns in the deblurred predictions, we designed a different version of DeblurGAN.
We replaced each of the transposed convolutional layers in the original DeblurGAN architecture with a nearest-neighbor upsampling layer followed by a regular convolutional layer.
The resulting generator structure can be seen in Figure \ref{dg_structure}.
For completeness and comparability, we conducted separate experiments using both DeblurGAN versions.
\begin{figure}
	\centering
	\includegraphics[width=0.85\linewidth]{DG_structure.pdf}
	\caption{Generator structure of the two different DeblurGAN-based enhancement architectures. a) Regular structure as introduced by Kopyn \textit{et~al.} \cite{Kopyn2018}. b) Modified structure according to the suggestions of Odena \textit{et~al.} \cite{odena2016}.}
	\label{dg_structure}
\end{figure}

\subsection{SRGAN}
The second method we used to enhance the frames predicted by FutureGAN is a GAN-based approach for image super-resolution, the SRGAN \cite{Ledig2016}.
Image super-resolution means that a low resolution (LR) image is upsampled to its high-resolution (HR) version.
The SRGAN was designed to generate HR images of high perceptual quality, which are upsampled by a factor of 4 from the LR images.
An increased resolution of the traffic scene predictions might also have positive effects on the object detection results because of the increased number of details in the high-resolution image.

The SRGAN loss is similar to the DeblurGAN loss (\cf Eq. \ref{eq:dgloss}).
It also contains both an adversarial and a content loss term.
The content loss is defined as in Eq. \ref{dgcontentloss} as the $L_2$ difference of the feature maps of a specific VGG-19 layer.
In image super-resolution, the task is to recover high-frequency components, therefore
Ledig \etal \cite{Ledig2016} chose a deeper VGG-19 convolutional layer ($VGG_{5,4}$) to calculate the content loss.
Similar as for DeblurGAN, the VGG-19 based content loss was chosen to learn perceptually meaningful representations for generating images of high visual quality.
In the original experiments, SRGAN was able to recover high-level details in the images quite well and achieved high human rating based \emph{mean-opinion scores (MOS)}.
For the detailed structure, we refer the reader to the original paper \cite{Ledig2016}.

\section{Experiments and Evaluation}
To evaluate the different enhancement methods for traffic scene prediction, the networks were trained on the Cityscapes dataset \cite{cordts2016}.
This dataset consists of 30 frame long \SI{16}{\bit} color videos, which were recorded with a frame rate of \SI{17}{\fps} in 50 different German cities.
The training split contains \num{2975} videos, the test split \num{1525}.

For generating our initial predictions, we first trained FutureGAN according to the procedure described by Aigner and K\"orner \cite{Aigner2018}.
The network was trained to predict five output frames from five input frames, thus the training and test sets contained \num{8924} and \num{4574} sequences, respectively.
To avoid any overlap between the training and test split for all further experiments on the enhancement methods, we continued using only the Cityscapes test split as a database.
We separated the new dataset into an 80:20 train-test split, leading to \num{3659} training sequences and \num{915} test sequences.
The original input frames of size \SI{2048 x 1024}{\px} were downsampled bicubically to \SI{128 x 128}{\px} in all cases except for the ground truth frames for the SRGAN experiments, which were downsampled bicubically to \SI{512 x 512}{\px}.
All networks are implemented in either PyTorch or Tensorflow for Python.

The training was performed on a single NVIDIA TITAN X Pascal GPU with \SI{12}{\giga\byte} of RAM separately for each network.
We used the \emph{ADAM} optimizer \cite{kingma2015} for all networks.
FutureGAN trained for 140 epochs with a gradually decaying learning rate of initially $l=0.001$ and $\beta_1 = 0.0$.
Both DeblurGAN versions trained for 300 epochs with $\beta_1=0.5$ and an initial learning rate of $l=0.0001$ which gradually decayed to zero after 150 epochs.
SRGAN was trained for 10 initialization epochs using the content loss and then for 300 full epochs with a learning rate of $0.0001$ and $\beta_1 = 0.9$.

After training, we evaluated the different prediction methods on our test split.
For the plain predictions, we used the trained FutureGAN network to generate a set of five future frames from a set of five input frames.
To test the different enhancement methods, we generated five predictions using FutureGAN and then enhanced each of the five frames using the different image-to-image translation networks.
In total, we evaluated four different prediction pipelines: plain FutureGAN (no enhancement), FutureGAN + DeblurGAN (transposed convolution), FutureGAN + DeblurGAN (upsample + convolution), and FutureGAN + SRGAN.
In order to get an estimate of the inference time that it takes for predicting five future frames with each of the prediction pipelines, the following list provides the average values over the whole test set on an NVIDIA GeForce RTX 2070 GPU with \SI{8}{\giga\byte} of RAM:
\begin{itemize}
\item FutureGAN: \SI{0.011}{\second}
\item FutureGAN + DeblurGAN (trconv): \SI{0.019}{\second}
\item FutureGAN + DeblurGAN (ups+conv): \SI{0.020}{\second}
\item FutureGAN + SRGAN: \SI{0.707}{\second}
\end{itemize}
The SRGAN needs the most time to generate five predictions, most likely due to the increased frame size of the outputs.

\subsection{Qualitative Results}
Figure \ref{cityscapes} shows a qualitative comparison of the prediction results for two different video sequences.
For each of the two sequences, we display the input frames, the corresponding ground truth predictions, the prediction results of FutureGAN without any enhancement, and the results for the three different enhancement approaches.
\begin{figure*}
	\centering
	\includegraphics[width=\linewidth]{Results_enhancing.pdf}
	\caption{Prediction results for the Cityscapes test sequences. a: Input, b: Ground Truth, c: FutureGAN \cite{Aigner2018}, d: DeblurGAN \cite{Kopyn2018} (transposed convolutions), e: DeblurGAN (NN-upsampling + convolution), f: SRGAN \cite{Ledig2016}.}
	\label{cityscapes}
\end{figure*}
The differences between the enhancement methods are clearly visible.
When using the original DeblurGAN architecture to enhance the predicted frames, the checkerboard pattern mentioned in section \ref{sec:deblurgan} can be seen in Figure \ref{cityscapes} d.
Using the modified DeblurGAN with nearest-neighbor upsampling followed by regular convolutional layers reduces this pattern in the enhanced frames.
In general, both DeblurGAN versions lead to an improved object appearance in all frames.
Although there still remain unclear object boundaries after enhancing the frames, especially the cars and lane markings appear smoothed and straightened in comparison to the plain FutureGAN predictions.
We further observed that the DeblurGAN architecture learned to generate object-specific features, such as the red colored taillights of cars (see figure \ref{cityscapes}).
In contrast to that, the SRGAN-enhancement does not seem to produce a more realistic version of the predictions.
The SRGAN learned to add high-frequency details to the image which do not match the original details.  This effect is probably caused by the content loss that is calculated with deeper VGG-19 feature maps.
Even though SRGAN also generates object-specific features such as red taillights, the overall visual quality of the predicted frames seems best after the enhancement with the modified DeblurGAN (see Figure \ref{cityscapes} e).

\subsection{Quantitative Results: Traditional Metrics}
A traditional way to quantitatively evaluate the enhanced predictions is to calculate image comparison metrics, such as the \emph{mean squared error (MSE)}, the \emph{peak signal-to-noise ratio (PSNR)}, and the \emph{structural similarity index (SSIM)}.
For these evaluations, the resulting images are compared with the ground truth image of size \SI{128 x 128}{\px}, except for the case of SRGAN, where the comparison is on the increased size of \SI{512 x 512}{\px}.
The average values over all five frames are provided in Table \ref{table:metrics}.
Additionally, we plotted the trends of the MSE, PSNR and SSIM values per predicted frame in figure \ref{quantitative}.

\begin{table}
	\caption{Average results over 5 frames for all enhancement methods (best results in bold)}
	\label{table:metrics}
	\centering
	\begin{tabular}{lrrr}
		\cmidrule(r){1-4}
		& \multicolumn{1}{c}{MSE} & \multicolumn{1}{c}{PSNR} & \multicolumn{1}{c}{SSIM} \\
		\cmidrule(r){1-4}
		FutureGAN \cite{Aigner2018}				& \textbf{0.0252} 	& \textbf{22.3829}	& \textbf{0.6094}\\
		DeblurGAN \cite{Kopyn2018} (trconv)		& 0.0295				& 21.5902    				& 0.5266\\
		DeblurGAN (ups+conv)					& 0.0275				& 21.9507    				& 0.5907\\
		SRGAN \cite{Ledig2016}					& 0.0372 				& 20.4893   				& 0.4900 \\
		\cmidrule(r){1-4}
	\end{tabular}
\end{table}

\begin{figure*}
	\centering
	\subfigure{
		\includegraphics[width=0.3\linewidth]{mse.pdf}
		\label{mse}}
	\subfigure{
		\includegraphics[width=0.3\linewidth]{psnr.pdf}
		\label{psnr}}
	\subfigure{
		\includegraphics[width=0.3\linewidth]{ssim.pdf}
		\label{ssim}}
	\caption{Quantitative results per predicted frame for all enhancement methods (DG = DeblurGAN).}
	\label{quantitative}
\end{figure*}

In general, the MSE, PSNR, and SSIM show worse results the higher the frame number.
This was expected since a higher frame number represents a prediction further into the future.
Looking in detail at the values, the non-enhanced FutureGAN predictions yield the best values (lower for MSE and higher for PSNR and SSIM).
Enhancing the predictions using the modified DeblurGAN version (see Figure \ref{dg_structure} b) gives the second best results for all three metrics.
When comparing the results of these traditional metrics, they seem contrary to the visual impression of the frames in figure \ref{cityscapes}.
The traditional metrics can apparently not represent the human perception of improvement.
Figure \ref{cityscapes} shows this, when comparing the plain FutureGAN predictions (see Figure \ref{cityscapes} c) to the enhanced predictions of the modified DeblurGAN (see Figure \ref{cityscapes} e).

\subsection{Quantitative Results: Object Detection}
\begin{figure*}[t]
	\centering
	\includegraphics[width=.95\linewidth]{Yolo_results.pdf}
	\caption{Object detection results of YOLOv3 \cite{redmon2018} from different video sequences at the five different time steps. a: Ground truth, b: plain FutureGAN \cite{Aigner2018}, c: DeblurGAN \cite{Kopyn2018} (upsample+convolution) enhanced prediction.}
	\label{Yolo}
\end{figure*}
To quantify the perceived visual improvement of the enhancement methods, especially also in the context of traffic scene prediction, we evaluated the images using a state-of-the-art object detection network, YOLOv3 \cite{redmon2018}.
The network outputs bounding boxes and corresponding class labels.
For evaluating the precision and recall of the object detection we take the detections on the ground truth frames as ground truth bounding boxes.
This means the evaluation is relative with respect to the detection results of the algorithm on the ground truth images.

Figure \ref{Yolo} shows the qualitative results of the object detection network for four images.
For brevity, we now only show the best performing enhancement method, the modified DeblurGAN (upsample + convolution), the plain FutureGAN predictions, and the ground truth frames.
In these examples, one can see that, especially for the object class "car", the number of detections increases for the enhanced predictions in comparison with the non-enhanced predictions.
However, the object detection network has problems detecting the class "person" in the enhanced images.
An example of this is also shown in figure \ref{Yolo}.

\begin{figure}[h]
	\centering
	\includegraphics[width=0.9\linewidth]{CarAP_frames.pdf}
	\caption{Average precision of the class "car" per predicted frame for all enhancement methods (DG = DeblurGAN).}
	\label{carAP}
\end{figure}
Since the class "car" is by far the most common class in our dataset, we specifically look at the average precision (AP) values of this class.
We calculate the AP as defined in \cite{everingham2010} with an IoU threshold of 50\% counting as correctly detected.
Figure \ref{carAP} shows the development of the values per predicted frame for each of the prediction methods.
For all methods, the general trend is a declining AP for an increased number of prediction steps, but the slow decrease suggests that cars are preserved well in the predicted frames.
Additionally, the qualitatively best performing enhancement method, DeblurGAN (upsample + convolution), shows the highest AP values for all five frames, which confirms the visual impression of the results.
The SRGAN enhancement exhibits the lowest values throughout, which is also in accordance with the visual impression of the prediction results.

\section{Conclusions and Discussion}
In this paper, we evaluated the capabilities of GAN-based methods, SRGAN and DeblurGAN, to enhance video frame predictions of another generative model, FutureGAN.
While, in general, motion representations and the difference between the movement of foreground and background objects are learned by FuturGAN, the predictions suffer from blurring effects on the moving objects, leading to irregular shapes and over-smoothed object details.
In order to correct these effects, we used established image-to-image translation models to generate enhanced versions of the predicted frames.
The networks were trained on the Cityscapes dataset to use them for traffic scene prediction.
We evaluated the different enhancement methods especially regarding their positive effects on object detection results, using a state-of-the-art object detector, the YOLOv3.

The visual quality of the enhanced predictions varies greatly between the enhancement methods.
DeblurGAN shows a straightening effect, especially on car shapes and lane markings, leading to visually more realistic results.
Additionally, the network learns to include object-specific features such as car taillights, which initially were averaged out in the prediction results of FutureGAN.
In contrast, SRGAN mainly learns to add high-frequency features to the enhanced image, which results in  unrealistic edges and patterns in the objects.
These differences are most likely caused by the different content losses of DeblurGAN and SRGAN.
While both networks use a very similar approach to calculate the content loss, DeblurGAN uses an earlier VGG-19 layer, SRGAN uses a deeper layer.
With the low frame resolution in mind, a lower VGG-19 layer might be better for capturing the general content of the image.

We evaluated the enhanced frame predictions using traditional image comparison metrics, but they failed to resemble the visual impression and showed no improvement for any of the enhancement methods.
The evaluation of the object detection capabilities with YOLOv3, on the other hand, confirms the visual impression.
The enhancement method that produced the qualitatively best predictions, DeblurGAN (upsample + convolution), yielded the best detection performance.
Even though pedestrians got over-smoothed by the enhancement network, possibly due to the low resolution of the images or the small number of training examples, the positive enhancement effect on cars is substantial.
The average precision for detecting cars could be increased significantly in the enhanced predictions compared with the regular predictions.
This verifies the application of image-to-image translation models for enhancing predictions of traffic scenes.

\bibliographystyle{ieee}