Bases for counting functions
on free monoids and groups

Petr Kiyashko

###### Abstract

The focus of this paper is providing a description of the spaces of counting
functions on free monoids and groups and of the Brooks space. These results
have been originally obtained in [1], however one of the theorems at the time
of writing this paper contained a slight error, and we correct it here. We
also propose alternative, simpler proofs to the main theorems from [1].

##  1 Introduction

#####

Let $S=\\{a_{1},a_{2},\dots a_{n}\\}$ be a finite set of letters with $n\geq
2$. We define the free monoid of rank $n$ as the set of all finite words over
the alphabet $S$ (including the empty word, denoted by $\epsilon$), and denote
it by $M_{n}$. We denote by $|w|$ the length of the word $w\in M_{n}$, and by
$w_{i}$ the $i$-th letter of the word, with $1$ being the first index
(sometimes the $i$-th word of a set of words may also be denoted by $w_{i}$,
but it is always clear from the context which meaning we are referring to). We
denote by $w_{fin}$ last letter of $w$ (i. e. $w_{|w|}$) and by $w_{fin-i}$ we
denote the letter $w_{|w|-i}$. A word $v$ is a subword of another word $w$ if
for some letter index $i\leq|w|-|v|+1$ it holds that $v=w_{i}w_{i+1}\ldots
w_{i+|v|-1}$. For any word $w\in M_{n}$ and $k\geq 0$ we define the $k$-th
power of $w$ as the word obtained by concatenating $k$ copies of $w$ and
denote it by $w^{k}$.

#####

Similarly, let $\bar{S}=\\{a_{i},a_{i}^{-1}\mid a_{i}\in S\\}$, and we define
the free group of rank $n$ as the set of all reduced words over the alphabet
$\bar{S}$, and denote it by $F_{n}$. A word $w$ is called reduced if for all
$1\leq i\leq n$ the words $a_{i}a_{i}^{-1}$ and $a_{i}^{-1}a_{i}$ are not
subwords of $w$. The empty word is also included in $F_{n}$ by definition. The
length, the $i$-th letter of a reduced word, the subword relation between
reduced words in $F_{n}$ are defined similarly to the monoid case. For the
case of a reduced word $w\in F_{n}$ with $w_{1}\neq w_{fin}^{-1}$ the $k$-th
power of $w$ denoted by $w^{k}$ is also defined similarly to the monoid case.
We define the inverse of a reduced word $w$ as the word
$w^{-1}=w_{fin}^{-1}w_{fin-1}^{-1}\ldots w_{1}^{-1}$.

#####

Let us define the function $p_{v}(w)$ for $v,w\in M_{n}$ as the number of
occurrences of $v$ in $w$, i. e. the number of distinct indices $i$ such that
$v=w_{i}w_{i+1}\ldots w_{i+|v|-1}$. This function will be referred to as the
elementary $v$-counting function. For the free group $F_{n}$ the definition of
elementary counting functions is virtually identical, with an additional
requirement that the words $v$ and $w$ are necessarily reduced. We extend the
definition to the empty word as $p_{\epsilon}(w)=|w|$ in both cases.

Now, in the monoid case we define a counting function $f$ over a field
$\Re\in\\{\mathbb{Q},\mathbb{R},\mathbb{C}\\}$ as an arbitrary linear
combination of elementary counting functions with coefficients from $\Re$, i.
e.

$f=\sum_{i=1}^{m}x_{i}p_{w_{i}},\ x_{i}\in\Re\setminus\\{0\\},\ w_{i}\in
M_{n}.$ (1)

The functions $p_{w}$ map $M_{n}$ to $\mathbb{N}$, which in turn can be
naturally embedded in $\Re$, thus if we consider the elementary counting
functions to be maps from $M_{n}$ to $\Re$, then such linear combinations are
valid. Let us denote by $C(M_{n})$ the vector space of all counting functions.
The counting functions for $F_{n}$ and the space $C(F_{n})$ are defined
similarly. For a representation of some counting function $f$ of the form (1)
we define it’s depth as the maximum of $|w_{i}|$ over all words $w_{i}$. Now,
for any function $f\in C(M_{n})$ ($f\in C(F_{n})$) we define the depth of $f$
as the minimal depth over all the representations of $f$. It will be proven
further that if the depth of $f$ is non-zero, it has only one representation
of the form (1).

#####

We consider two counting functions $f_{1},f_{2}$ equivalent ($f_{1}\sim
f_{2}$) if their difference is bounded, i. e.
$||f_{1}-f_{2}||_{\infty}<\infty$. Note that this relation is linear, thus we
may define a quotient space. We denote by $\widehat{f}$ the equivalency class
of $f\in C(M_{n})$ ($f\in C(F_{n})$). We denote by $K(M_{n})$ (respectively
$K(F_{n})$) the set of all functions $f$ such that $\widehat{f}=\widehat{0}$,
i. e. the kernel of factorization by the relation $\sim$, and by
$\widehat{C}(M_{n})$ (respectively $\widehat{C}(F_{n})$) we denote the vector
space of classes of functions $\widehat{f}$ for all $f\in C(M_{n})$ ($f\in
C(F_{n})$), i. e. the image of factorization by the relation $\sim$.

#####

Finally, let us define the Brooks space. A Brooks quasimorphism is defined as

$\phi_{w}=p_{w}-p_{w^{-1}}$

for some reduced word $w\in F_{n}$ with $|w|\geq 1$. We define the Brooks
space $Br(F_{n})$ as the space of all linear combinations of Brooks
quasimorphisms with coefficients from $\Re$. Two elements of the Brooks space
are considered equivalent ($\sim$) if their difference is bounded. The
quotient space $\widehat{Br}(F_{n})$ is defined similarly to the monoid and
group case. Now consider the following linear mappings:
$\sigma_{1}:C(F_{n})\rightarrow Br(F_{n})$, $\sigma_{1}(p_{w})=\phi_{w}$ and
$\sigma_{2}:Br(F_{n})\rightarrow\widehat{Br}(F_{n})$,
$\sigma_{2}(\phi_{w})=\widehat{\phi_{w}}$, and their composition
$\sigma=\sigma_{2}\circ\sigma_{1}$,
$\sigma:C(F_{n})\rightarrow\widehat{Br}(F_{n})$.

${C(F_{n})}$${Br(F_{n})}$${\widehat{C}(F_{n})}$${\widehat{Br}(F_{n})}$$\scriptstyle{\sigma}$$\scriptstyle{\sigma_{1}}$$\scriptstyle{\sigma_{2}}$
Figure 1: Commutative diagram for $\sigma_{1}$, $\sigma_{2}$ and $\sigma$

We define the kernel space $K_{Br}(F_{n})$ as the kernel of $\sigma$. Note
that

$K_{Br}=\operatorname{Ker}\sigma=(\operatorname{Ker}\sigma_{1})+\sigma_{1}^{-1}(\operatorname{Ker}\sigma_{2}).$
(2)

#####

In this paper we sometimes refer to $C(M_{n})$ and $C(F_{n})$ as $C$, to
$\widehat{C}(M_{n})$ and $\widehat{C}(F_{n})$ as $\widehat{C}$ and to
$K(M_{n})$ and $K(F_{n})$ as $K$. Whether we are referring to the monoid case,
the group case or both simultaneously, should be clear from context. We also
refer to $Br(F_{n})$, $\widehat{Br}(F_{n})$ and $K_{Br}(F_{n})$ as $Br$,
$\widehat{Br}$ and $K_{Br}$ respectively.

#####

The aim of this paper is describing spanning sets of $K(M_{n}),K(F_{n})$ and
$K_{Br}$, identifying bases of $\widehat{C}(M_{n}),\widehat{C}(F_{n})$ and
$\widehat{Br}$, and providing simpler proofs of these descriptions.

###  1.1 Motivations

#####

The descriptions of the kernels and the bases were first laid out in [1], and
the Brooks space was first introduced in [3]. A description of it’s basis may
also be found in [1], and since this basis is infinite, this leads to the fact
that dim $H_{b}^{2}(F_{n};\mathbb{R})=\infty$, which Brooks tried to prove,
and which has been proven in [4] by constructing an infinite set of linearly
independent classes of Brooks quasimorphisms. Larger sets have been since
provided in [5] and [6]. However, these sets were not bases of
$\widehat{Br}(F_{n})$, and an explicit basis has been first identified in [1].
The proofs given in this paper were relatively complicated and lengthy,
therefore we tried to find shorter and simpler alternatives. Moreover, the
description of the basis of $\widehat{C}(F_{n})$ in [1] at the moment of
writing this paper contained one extra element, which rendered the provided
set linearly dependent, and we provide an updated description. Alas, while
quasimorphisms on free groups have been extensively researched, the same can
not be said about quasimorphisms on free monoids, thus the aforementioned
descriptions in the case of $M_{n}$ may prove useful in future research.

#####

The descriptions of kernels $K$ and bases of $\widehat{C}$ are also used in
algorithms that check whether two counting functions are equivalent. One pen-
and-paper algorithm for this problem has been proposed in [1], and a formal
algorithm that is efficient for free groups of rank $\geq 2$ and free monoids
of rank $\geq 3$ has been described in [2]. Such algorithms may be used to
explore the action of Out($F_{n}$) on $H_{b}^{2}(F_{n};\mathbb{R})$, namely
fixed points, as has been done in [7]. Similar applications may be found in
the case of quasimorphisms on $M_{n}$, though this case has not been explored
yet.

###  1.2 Acknowledgements

This paper is almost identical with my bachelor’s thesis at the Higher School
of Economics university from 2023. I would like to thank my scientific advisor
Alexey Talambutsa for the assistance in writing the thesis. I would also like
to thank Tobias Hartnick and Antonius Hase for their reviews and valuable
corrections that helped polish the paper.

###  1.3 Main results

####  1.3.1 Kernel and basis

######  Definition 1.1 (from theorem 1.3, [1]).

For a word $w\in M_{n}$ we define the left and right extension relations as
counting functions $l_{w}$ and $r_{w}$ of the following form:

$l_{w}=p_{w}-\sum_{s\in S}p_{sw},\ r_{w}=p_{w}-\sum_{s\in S}p_{ws}.$

######  Definition 1.2 (from theorem 1.3, [1]).

Similarly, for a reduced word $w\in F_{n}$ we define the left and right
extension relations as follows:

$l_{w}=p_{w}-\sum_{s\in\bar{S}\setminus\\{w_{1}^{-1}\\}}p_{sw},\
r_{w}=p_{w}-\sum_{s\in\bar{S}\setminus\\{w_{fin}^{-1}\\}}p_{ws}.$

######  Definition 1.3 (partially from theorem 1.3, [1]).

For a reduced word $w\in F_{n}$ we define the symmetry relation
$s_{w}=p_{w}+p_{w^{-1}}$. We also define the symmetrized extension relation
$se_{w}=l_{w}-r_{w^{-1}}$.

######  Theorem 1.4 (Kernel, theorem 1.3, [1]).

:
1) $K(M_{n})$ is spanned by $\\{l_{w},r_{w}\mid w\in M_{n}\\}$.
2) $K(F_{n})$ is spanned by $\\{l_{w},r_{w}\mid w\in F_{n}\\}$.
3) $K_{Br}(F_{n})$ is spanned by $\\{s_{w},se_{w}\mid w\in F_{n}\\}$.

######  Theorem 1.5 (Basis, theorem 1.5, [1], corrected).

:
1) Let $W$ be the set of all words $w\in M_{n}$, including $\epsilon$, such
that $w_{1}\neq a_{1}$ and $w_{fin}\neq a_{1}.$ Then the set
$B=\\{\widehat{p_{w}}\mid w\in W\\}$ is a basis of $\widehat{C}(M_{n})$.

2) Similarly, let $\bar{W}^{\prime}$ be the set of all reduced words $w\in
F_{n}$, also including $\epsilon$, such that $w_{1}\neq a_{1}$,
$w_{1}w_{2}\neq a_{2}a_{1}^{-1}$, $w_{fin}\neq a_{1}^{-1}$ and
$w_{fin-1}w_{fin}\neq a_{1}a_{2}^{-1}$. Now, we define
$\bar{W}=\bar{W}^{\prime}\cup\\{a_{1}^{-1}\\}\ \setminus\ \\{a_{2}\\}$. Then
the set $\bar{B}=\\{\widehat{p_{w}}\mid w\in\bar{W}\\}$ is a basis of
$\widehat{C}(F_{n})$.

3) Let $W_{Br}^{\prime}=\bar{W}\cup\\{a_{1},a_{2}\\}\ \setminus\
\\{\epsilon\\}$. Now, let $W_{Br}$ be a subset of $W_{Br}^{\prime}$ such that
for every $w\in W_{Br}^{\prime}$ it holds that $|\\{w,w^{-1}\\}\cap W_{Br}|=1$
(i. e. for every word in $W_{Br}^{\prime}$ the set $W_{Br}$ either contains
the word, or it’s inverse). Then $B_{Br}=\\{\widehat{\phi_{w}}\mid w\in
W_{Br}\\}$ is a basis of $\widehat{Br}$.

These two theorems have already been laid down and proven in [1] , with the
difference being that $a_{2}$ was also included in the $\bar{W}$ set for the
case of $F_{n}$, which is corrected here, and that the spanning set of
$K_{Br}$ provided here is more precise (in the original paper it was described
as $\\{s_{w},l_{w},r_{w}\mid w\in F_{n}\\}$). Our main focus is attempting to
provide shorter and simpler proofs for these facts.

###  1.4 Preliminaries

######  Lemma 1.6.

Elementary counting functions for words of non-zero length form a basis of
$C(M_{n})$ (respectively $C(F_{n})$).

###### Proof.

All elementary counting functions span $C$ by definition, and
$p_{\epsilon}=\sum_{|w|=1}p_{w}$, thus the aforementioned set also spans the
space. Now, let us take a non-trivial linear combination of elementary
counting functions for words of non-zero length,

$f=\sum_{i=1}^{m}x_{i}p_{w_{i}},$

and let $i$ be the index of the shortest word $w_{i}$ in it. Then
$f(w_{i})=x_{i}$, thus $f\not\equiv 0$. ∎

######  Corollary 1.7.

Let $W^{\prime}=F_{n}\ \setminus\ \\{\epsilon\\}$. Now let $W$ be a subset of
$W^{\prime}$ such that for every $w\in W^{\prime}$ it holds that
$|\\{w,w^{-1}\\}\cap W|=1$. Then $\\{\phi_{w}\mid w\in W\\}$ is a basis of
$Br(F_{n})$.

######  Lemma 1.8.

For any word $w\in M_{n}$ (reduced word $w\in F_{n}$) the left and right
extension relations $l_{w}$, $r_{w}$ lie in $K$.

###### Proof.

Let us only provide the proof for $M_{n}$, since for $F_{n}$ it is virtually
identical. Any counting function is $0$ at $\epsilon$, thus for boundedness we
only consider arguments of non-zero length. For words $w$ and $v$, with
$|v|\geq 1$

$p_{w}(v)=[w=v_{1}\ldots v_{|w|}]+p_{w}(v_{2}\ldots v_{fin})$

(the number of subwords of $v$ equal to $w$ that do not start with the first
letter of $v$ plus $1$ if $w$ is a prefix of $v$). Every subword counted in
$p_{w}(v_{2}\ldots v_{fin})$ is preceded by some letter in $v$, thus

$p_{w}(v_{2}\ldots v_{fin})=\sum_{s\in S}p_{sw}(v),$

therefore $l_{w}(v)=p_{w}(v)-p_{w}(v_{2}\ldots v_{fin})=[w=v_{1}\ldots
v_{|w|}]$ may be equal to $1$ or $0$, thus $l_{w}$ is bounded. The boundedness
of $r_{w}$ may be proven similarly by using the last letter of $v$ instead of
the first. ∎

######  Definition 1.9.

We define $\delta_{1}(w,v)=[w=v_{1}\ldots v_{|w|}]$, i. e. as $1$ if $v$
starts with $w$, and $0$ otherwise. Similarly, we define
$\delta_{fin}(w,v)=[w=v_{fin-|w|+1}\ldots v_{fin}]$, i. e. as $1$ if $v$ ends
with $w$, and $0$ otherwise. It is clear from the proof above that
$l_{w}(v)=\delta_{1}(w,v)$ and $r_{w}(v)=\delta_{fin}(w,v)$.

######  Lemma 1.10.

For any reduced word $w\in F_{n}$ the symmetry relation and the symmetrized
extension relation $s_{w}$, $se_{w}$ lie in $K_{Br}$.

###### Proof.

First,

$\sigma(s_{w})=\widehat{\phi_{w}}+\widehat{\phi_{w^{-1}}}=\widehat{p_{w}}-\widehat{p_{w^{-1}}}+\widehat{p_{w^{-1}}}-\widehat{p_{w}}=\widehat{0},$

therefore $s_{w}\in K_{Br}$. Now,

$\sigma(se_{w})=\widehat{\phi_{w}}-\sum_{s\in\bar{S}\setminus\\{w_{1}^{-1}\\}}\widehat{\phi_{sw}}-\Bigl{(}\widehat{\phi_{w^{-1}}}-\sum_{s\in\bar{S}\setminus\\{w_{1}\\}}\widehat{\phi_{w^{-1}s}}\Bigr{)}=$
$(\widehat{\phi_{w}}-\widehat{\phi_{w^{-1}}})-\sum_{s\in\bar{S}\setminus\\{w_{1}^{-1}\\}}(\widehat{\phi_{sw}}-\widehat{\phi_{w^{-1}s^{-1}}})=2\widehat{\phi_{w}}-2\sum_{s\in\bar{S}\setminus\\{w_{1}^{-1}\\}}\widehat{\phi_{sw}}=$
$2\Bigl{(}\widehat{p_{w}}-\sum_{s\in\bar{S}\setminus\\{w_{1}^{-1}\\}}\widehat{p_{sw}}-\Bigl{(}\widehat{p_{w^{-1}}}-\sum_{s\in\bar{S}\setminus\\{w_{1}^{-1}\\}}\widehat{p_{w^{-1}s^{-1}}}\Bigr{)}\Bigr{)}=2(\widehat{l_{w}}-\widehat{r_{w^{-1}}}),$

and it follows from Lemma 1.8 that $l_{w}$ and $r_{w}$ are bounded, thus
$se_{w}\in K_{Br}$ too. ∎

##  2 Spanning sets of $\widehat{C}$

In this section we prove that the sets $B$, $\bar{B}$ and $B_{Br}$, defined in
Theorem 1.5, are spanning sets of $\widehat{C}(M_{n})$, $\widehat{C}(F_{n})$
and $\widehat{Br}(F_{n})$ respectively. In the next section we will prove that
the aforementioned sets are linearly independent. In this section we write
$p_{w}$ instead of $\widehat{p_{w}}$, since we will be only working with
equivalency classes of functions.

###  2.1 Monoid case

######  Lemma 2.1.

$B$ is a spanning set of $\widehat{C}(M_{n})$.

###### Proof.

Let us prove that all the elementary counting functions of non-empty words lie
in the span of $B$. Any word $w\in M_{n}$ with $|w|\geq 0$ can be represented
as $w=a_{1}^{k}va_{1}^{m}$ with $|v|\geq 0$, $v_{1}\neq a_{1}$, $v_{fin}\neq
a_{1}$ and $k,m\geq 0$. Let us define $||w||=k+m$. Note that if $w=a_{1}^{d}$
the choice of $k$ and $m$ is ambiguous, but $||a_{1}^{d}||=d$, thus the
definition is correct. In this special case we presume $k=1$ and $m=||w||-1$.
Now, we prove that for any word $w$ with $|w|\geq 1$ the function class
$p_{w}$ lies in the span of $B$ inductively by $||w||$.

#####

For $||w||=0$ it holds that $w_{1}\neq a_{1}$ and $w_{fin}\neq a_{1}$, thus
$p_{w}\in B$ by definition.

#####

Now let us prove the induction step. Consider it known that for any word $w$
with $||w||\leq d$ the function $p_{w}$ belongs to the span of $B$. Let
$w^{\prime}=a^{k}_{1}wa^{m}_{1}$ with $||w^{\prime}||=k+m=d+1$. If $k>0$, then
by the left extension relation

$p_{w^{\prime}}=p_{a^{k}_{1}wa^{m}_{1}}=p_{a^{k-1}_{1}wa^{m}_{1}}-\sum_{s\in
S\setminus\\{a_{1}\\}}p_{sa^{k-1}_{1}wa^{m}_{1}}.$

If $|w|>0$, then $||a^{k-1}_{1}wa^{m}_{1}||=k-1+m=d$ and
$||sa^{k-1}_{1}wa^{m}_{1}||=m\leq d$ (since $s\neq a_{1}$). Otherwise, $k=1$,
thus $||a^{k-1}_{1}wa^{m}_{1}||=||a^{m}_{1}||=m=d$ and
$||sa^{k-1}_{1}wa^{m}_{1}||=||sa^{m}_{1}||=m=d$. Therefore all the terms on
the left side lie in the span of $B$ by the induction hypothesis, and
$p_{w^{\prime}}$ also lies in the span.

#####

Now if $k=0$, then $|w|>0$ and $m>0$. In this case $w^{\prime}=wa^{m}_{1}$ and
by the right extension relation

$p_{w^{\prime}}=p_{wa^{m}_{1}}=p_{wa^{m-1}_{1}}-\sum_{s\in
S\setminus\\{a_{1}\\}}p_{wa^{m-1}_{1}s}.$

In this case $||wa_{1}^{m-1}||=m-1=d$ and $||wa^{m-1}_{1}s||=0$, thus
$p_{w^{\prime}}$ lies in the span again.

#####

Therefore for all the words $w\in M_{n}$ with $|w|\geq 1$ the class $p_{w}$
lies in the span of $B$, thus by Lemma 1.6 the whole space
$\widehat{C}(M_{n})$ is spanned by $B$. ∎

###  2.2 Group case

######  Lemma 2.2.

$\bar{B}$ is a spanning set of $\widehat{C}(F_{n})$.

###### Proof.

The idea of the proof is the same as in the monoid case. However, it requires
a little more legwork since there are more cases.

#####

As a preliminary step, let us prove that $p_{a_{2}}$ lies in the span of
$\bar{B}$.

######  Proposition 2.3.

The counting function

$f=\sum_{s\in\bar{S}\setminus\\{a_{1},a_{1}^{-1}\\}}p_{s}-\sum_{\begin{subarray}{c}s_{1}\in\bar{S}\setminus\\{a_{1}\\},\\\
s_{2}\in\bar{S}\setminus\\{a_{1}^{-1},s_{1}^{-1}\\}\end{subarray}}p_{s_{1}s_{2}}$

lies in $K(F_{n})$.

###### Proof.

Let us subtract $\sum_{s\in\bar{S}\setminus\\{a_{1},a_{1}^{-1}\\}}l_{s}$ from
$f$. In this expression chain all the letters $s,s_{1},s_{2}$ are presumed to
lie in $\bar{S}$ (thus all the sums are finite) and all the words are presumed
to be reduced so as not to specify $s\in\bar{S}$, $s_{1}\in\bar{S}$ and
$s_{2}\in\bar{S}\setminus\\{s_{1}^{-1}\\}$ in every sum.

$f-\sum_{s\neq a_{1},a_{1}^{-1}}l_{s}=\sum_{s\neq
a_{1},a_{1}^{-1}}p_{s}-\sum_{s\neq a_{1},a_{1}^{-1}}l_{s}-\sum_{s_{1}\neq
a_{1},s_{2}\neq a_{1}^{-1}}p_{s_{1}s_{2}}=$ $\sum_{s\neq
a_{1},a_{1}^{-1}}p_{s}-\sum_{s\neq a_{1},a_{1}^{-1}}p_{s}+\sum_{s_{2}\neq
a_{1},a_{1}^{-1}}p_{s_{1}s_{2}}-\sum_{s_{1}\neq a_{1},s_{2}\neq
a_{1}^{-1}}p_{s_{1}s_{2}}=$ $\sum_{s\neq
a_{1},a_{1}^{-1}}p_{a_{1}s}-\sum_{s\neq
a_{1},a_{1}^{-1}}p_{sa_{1}}=\sum_{s\neq
a_{1},a_{1}^{-1}}p_{a_{1}s}-\sum_{s\neq
a_{1},a_{1}^{-1}}p_{sa_{1}}+p_{a_{1}a_{1}}-p_{a_{1}a_{1}}=$ $\sum_{s\neq
a_{1}^{-1}}p_{a_{1}s}-\sum_{s\neq
a_{1}^{-1}}p_{sa_{1}}=l_{a_{1}}-r_{a_{1}}\sim 0.$

Therefore $f\sim 0$. ∎

All the terms in $f$ except $p_{a_{2}}$ lie in $\bar{B}$, therefore
$p_{a_{2}}\sim p_{a_{2}}-f\in$ span $\bar{B}$.

#####

Now, let us introduce a few definitions. Let $P=\\{a_{1},\
a_{2}a_{1}^{-1}\\}$, and $P^{\prime}=\\{a_{1}^{-1},\ a_{1}a_{2}^{-1}\\}$. Let
us introduce the set

$F_{P}=\\{a_{1}^{k}(a_{2}a_{1}^{-1})^{m}\mid k,m\geq 0\\}.$

Note, that words from $F_{P}$ are reduced as words of $F_{n}$, meaning that
$a_{1}$ and $a_{1}^{-1}$ do not stand next to each other and that all the
other words over the alphabet $P$ are not reduced in this sense. Similarly,
let

$F_{P^{\prime}}=\\{(a_{1}a_{2}^{-1})^{m^{\prime}}a_{1}^{-k^{\prime}}\mid
k^{\prime},m^{\prime}\geq 0\\}.$

It is also clear that this is precisely the subset of all the words over the
alphabet $P^{\prime}$ that are reduced as words of $F_{n}$.

#####

Then, for any word $w=a_{1}^{k}(a_{2}a_{1}^{-1})^{m}\in F_{P}$ we define
$|w|_{P}$ as $k+m$, and for any
$w^{\prime}=(a_{1}a_{2}^{-1})^{m^{\prime}}a_{1}^{-k^{\prime}}\in
F_{P^{\prime}}$ we define $|w^{\prime}|_{P^{\prime}}$ as
$k^{\prime}+m^{\prime}$.

#####

Now, let us extend the definitions of $|.|_{P}$ and $|.|_{P^{\prime}}$ to all
words in $F_{n}$. The word $w$ can be represented in two forms:

$w=a_{1}^{k}(a_{2}a_{1}^{-1})^{m}v$

and

$w=v^{\prime}(a_{1}a_{2}^{-1})^{m^{\prime}}a_{1}^{-k^{\prime}}$

with $k,m,k^{\prime},m^{\prime}\geq 0$. Let us define $|w|_{P}$ as $max(k+m)$
over all representations of the first form, and $|w|_{P^{\prime}}$ as
$max(k^{\prime}+m^{\prime})$ over all representations of the second form.
Finally, let us introduce a metric called defect of a word, defined as
follows:

$||w||=|w|_{P}+|w|_{P^{\prime}}=k+m+k^{\prime}+m^{\prime}.$

Further, we will refer to these values $k,m,k^{\prime},m^{\prime}$ of a word
$w$ as $k_{w},m_{w},k^{\prime}_{w},m^{\prime}_{w}$.

#####

Less formally, this metric can be described as the number of consecutive
patterns from $P$ at the beginning of the word plus the number of consecutive
patterns from $P^{\prime}$ at the end of the word.

#####

For example, $||a^{2}_{1}a_{2}a^{-1}_{1}a_{3}a_{1}a^{-1}_{2}||=4$. For
brevity, we extend this notation to the elementary counting functions, so that
$||p_{w}||=||w||$.

#####

It is important to note, that it does not always hold that

$w=a_{1}^{k_{w}}(a_{2}a_{1}^{-1})^{m_{w}}v(a_{1}a_{2}^{-1})^{m^{\prime}_{w}}a_{1}^{-k^{\prime}_{w}}$

for some word $v$. The cases, where this does not hold, are when a letter
$a_{1}$ participates in both $a_{1}^{k_{w}}$ and
$(a_{1}a_{2}^{-1})^{m^{\prime}_{w}}$:

$w=a_{1}^{k_{w}-1}(a_{1}a_{2}^{-1})^{m^{\prime}_{w}}a_{1}^{-k^{\prime}_{w}},$

and when $a_{1}^{-1}$ participates in $(a_{2}a_{1}^{-1})^{m_{w}}$ and
$a_{1}^{-k^{\prime}_{w}}$:

$w=a_{1}^{k_{w}}(a_{2}a_{1}^{-1})^{m_{w}}a_{1}^{-k^{\prime}_{w}+1}.$

#####

It is obvious that words of $0$ defect except $a_{2}$ lie in $\bar{W}$.
However, we have already proven that $p_{a_{2}}$ lies in the span, thus all
the counting functions for words of $0$ defect lie in the span of $\bar{B}$.
On the other hand, words of positive defect do not belong to $\bar{W}$, with
the only exception of $a_{1}^{-1}$. Now we prove that any elementary counting
function $p_{w}$ with $||w||>0$ and $w\neq a_{1}^{-1}$ can be reduced to a
linear combination of elementary counting functions with lesser defects by
right and left extension relations. If we prove that, then by induction any
elementary counting function will belong to $\bar{B}$.

#####

First, let us consider the case of words of form $w=a_{1}v$, meaning
$k_{w}>0$. Take an elementary counting function $p_{a_{1}v}$. For this
function the left extension relation can be written as

$p_{a_{1}v}=p_{v}-\sum_{s\in\bar{S}\setminus\\{a_{1},v_{1}^{-1}\\}}p_{sv}.$
(3)

First, we prove that $||p_{v}||<||p_{w}||$. It is clear that $k_{v}<k_{w}$,
because $v$ is obtained from $w$ by removing the first letter $a_{1}$ and
$m_{v}=m_{w},\ m^{\prime}_{v}\leq m^{\prime}_{w}$ and
$k^{\prime}_{v}=k^{\prime}_{w}$, thus $||p_{v}||<||p_{w}||$.

#####

Now, we prove that $||p_{sv}||<||p_{w}||$ for every term $p_{sv}$ in (3). In
order to do that, we have to calculate $||sv||$, where $s\neq
a_{1},v_{1}^{-1}$. The latter means that $k_{sv}=0<k_{w}$. Furthermore,
$m_{sv}=0\leq m_{w}$ even if $s=a_{2}$, because $v_{1}\neq a_{1}^{-1}$. Then,
$m^{\prime}_{sv}\leq m^{\prime}_{w}$, because $s\neq a_{1}$, so it can not
form a new $a_{1}a_{2}^{-1}$. Finally, if $|v|>0$, we have
$k^{\prime}_{sv}\leq k^{\prime}_{w}$, because $v_{1}\neq a_{1}^{-1}$. In the
case of $|v|=0$, i. e. $v=\epsilon$, and $s=a_{1}^{-1}$ we get
$p_{sv}=p_{s}=p_{a_{1}^{-1}}\in\bar{B}$ by definition, thus this term already
lies in the basis. This means that

$||p_{sv}||=k_{sv}+m_{sv}+k^{\prime}_{sv}+m^{\prime}_{sv}<k_{w}+m_{w}+k^{\prime}_{w}+m^{\prime}_{w}=||p_{w}||,$

which concludes the proof of the first case.

#####

Thus, we have established the proof of the induction step for elementary
counting functions of words with $k_{w}>0$. For counting functions of words
with $k^{\prime}_{w}>0$ ($w=va_{1}^{-1})$ this can be done symmetrically using
the right extension relations, with the only difference being that if
$|v^{\prime}|=0$ we already have $p_{w}=p_{a_{1}^{-1}}\in\bar{B}$ and no
additional proof is required.

#####

Now, we have to prove the induction step for the words of form
$w=a_{2}a_{1}^{-1}v$ ($k_{w}=0,\ m_{w}>0$). Again, by left extension relation

$p_{a_{2}a_{1}^{-1}v}=p_{a_{1}^{-1}v}-\sum_{s\in\bar{S}\setminus\\{a_{2},a_{1}\\}}p_{sa_{1}^{-1}v},$
(4)

and we again have to prove that all the terms on the right side are either of
lesser defect, than $n$, or can be explicitly reduced to a linear combination
of terms with lesser defect (in this case, not all terms have lesser defect
straight away).

#####

First, let us find the upper bound for $||p_{a_{1}^{-1}v}||$. Let us denote
$y=a_{1}^{-1}v$. Obviously, $k_{y}=0=k_{w}$ and $m_{y}=0<m_{w}$. It is also
clear that $k^{\prime}_{y}\leq k^{\prime}_{w}$ and $m^{\prime}_{y}\leq
m^{\prime}_{w}$, since $y$ is obtained from $w$ by removing the first letter,
thus $||p_{y}||<||p_{w}||$.

#####

Now, to the other terms, which have the form $sa_{1}^{-1}v=sy$ with $s\neq
a_{1},a_{2}$. Due to the restrictions on $s$ we have $k_{sy}=m_{sy}=0$, thus
$k_{sy}=k_{w}$ and $m_{sy}<m_{w}$. It also holds that
$m^{\prime}_{sy}=m^{\prime}_{w}$ since $s\neq a_{1}$ and thus no new
$a_{1}a_{2}^{-1}$ pattern could be formed. Now, the only case when
$k^{\prime}_{sy}>k^{\prime}_{w}$ is when $s=a_{1}^{-1}$ and
$w=a_{2}a_{1}^{-n+1}$. In this case, we have

$||sy||=||a_{1}^{-n}||=n=||a_{2}a_{1}^{-n+1}||=||w||.$

However, here $k^{\prime}_{w}>0$, thus $p_{w}$ can instead be reduced to a
linear combination of terms with lesser defects using the induction step for
the words of form $va_{1}^{-1}$, thus in this case $w$ also lies in $\bar{B}$.

#####

Finally, in the case if $k_{w}=m_{w}=k_{w}^{\prime}=0$ and $m_{w}^{\prime}>0$
we can again prove the induction step symmetrically using right extension
relations.

#####

Thus we have completed the proof of the induction step for all word forms, and
therefore in the group case $\bar{B}$ also spans $\widehat{C}(F_{n})$.

∎

###  2.3 Brooks space

######  Lemma 2.4.

$B_{Br}$ is a spanning set of $\widehat{B}$.

###### Proof.

Let $\phi_{w}=p_{w}-p_{w^{-1}}$ be the Brooks quasimorphism for some word $w$.
It follows from Lemma 2.2 that $p_{w}=\sum_{i=0}^{m}x_{i}p_{w_{i}}$ with
$p_{w_{i}}\in\bar{B}$. It is clear that
$p_{w^{-1}}=\sum_{i=0}^{m}x_{i}p_{w_{i}^{-1}}$, thus
$\phi_{w}=\sum_{i=0}^{m}x_{i}\phi_{w_{i}}$. Let us consider
$w_{i}\neq\epsilon$ for every $i$, since $\phi_{\epsilon}\equiv 0$. Now for
every $i$ either $w_{i}$ or $w_{i}^{-1}$ lies in $W_{Br}$. In the first case,
$\phi_{w_{i}}\in B_{Br}$. In the second case,
$x_{i}\phi_{w_{i}}=-x_{i}\phi_{w_{i}^{-1}}$, and $\phi_{w_{i}^{-1}}\in
B_{Br}$. Therefore if we define $I_{w}=\\{i\mid 0\leq i\leq m,w_{i}\in
W_{Br}\\}$ and $I_{w}^{-1}=\\{i\mid 0\leq i\leq m,w_{i}^{-1}\in W_{Br}\\}$,
then

$\phi_{w}=\sum_{i\in I_{w}}x_{i}\phi_{w_{i}}-\sum_{i\in
I_{w}^{-1}}x_{i}\phi_{w_{i}^{-1}}$

lies in the span, and $B_{Br}$ is indeed a spanning set of $\widehat{B}$. ∎

##  3 Linear independence of $B$, $\bar{B}$ and $B_{Br}$

###  3.1 Monoid case

######  Lemma 3.1.

The set $B$ is linearly independent.

###### Proof.

Let $f=\sum_{i=0}^{m}x_{i}p_{w_{i}}\in C(M_{n})$ be a linear combination of
elementary counting functions with $w_{i}\in W$ and $x_{i}\neq 0$. Let us
prove that $\widehat{f}\neq\widehat{0}$. For a word $u$ let $x_{u}$ be the
coefficient at this word in $f$ ($x_{u}$ may be zero). Let $w$ be one of the
the shortest words $w_{i}$, and let $L$ be the depth of $f$.

#####

First, we consider the case when $w=\epsilon$. In this case
$f(a_{1}^{k})=kx_{\epsilon}$, thus $f$ is not bounded.

#####

Now, if $|w|\geq 1$, let $v=wa_{1}^{L}$. Let us consider the word
$v^{k}=wa_{1}^{L}wa_{1}^{L}\ldots wa_{1}^{L}$ for some $k>0$. Every subword of
$v^{k}$ of length $l$ with $|w|\leq l\leq L$ is either equal to $w$, or starts
or ends with $a_{1}$. Therefore $f(v^{k})=kx_{w}\neq 0$, and $f$ is not a
bounded function.

#####

Now, since every non-trivial linear combination of functions in $B$ is not
equal to $\widehat{0}$, it follows that $B$ is linearly independent. ∎

###  3.2 Group case

######  Lemma 3.2.

The set $\bar{B}$ is linearly independent.

###### Proof.

Again, let $f=\sum_{i=0}^{m}x_{i}p_{w_{i}}\in C(F_{n})$ be a linear
combination of elementary counting functions with $w_{i}\in\bar{W}$ and
$x_{i}\neq 0$. Let us prove that $f$ is not bounded. We define $x_{u}$ and $L$
similarly to the free monoid case.

#####

First, let $x_{\epsilon}\neq 0$. In this case, again,
$f(a_{1}^{k})=kx_{\epsilon}$, and $f$ is not bounded.

#####

Second, let $x_{\epsilon}=0$ and $x_{a_{1}^{-1}}\neq 0$. Then
$f(a_{1}^{-k})=kx_{a_{1}^{-1}}$, and $f$ is not bounded.

#####

Now, let $x_{\epsilon}=0$, $x_{a_{1}^{-1}}=0$ and presume that $f$ is bounded.

######  Definition 3.3.

A reduced word $w$ with $|w|\geq 1$ is considered clean if $w_{1}\neq
a_{1},a_{1}^{-1}$ and $w_{fin}\neq a_{1},a_{1}^{-1}$.

######  Proposition 3.4.

Let $w$ be a clean word and let $v=wa_{1}^{L}$. Then $f(v^{k})=kf(v)$.
Similarly, if $v^{\prime}=a_{1}^{-L}w$, then $f(v^{\prime k})=kf(v^{\prime})$

###### Proof.

$v^{k}=wa_{1}^{L}wa_{1}^{L}\ldots wa_{1}^{L}$. Every subword of $v^{k}$ of
length $l\leq L$ either entirely lies in a copy of $v=wa_{1}^{L}$, or starts
with $a_{1}$. Since $x_{a_{1}^{k}u}=0$ for any $u$ and $k>0$, it indeed holds
that $f(v^{k})=kf(v)$. The proof for $v^{\prime}$ is virtually identical,
since it is also true that $x_{ua_{1}^{-k}}=0$ for any $u$ and $k>0$. ∎

Therefore if $f$ is bounded, then $f(wa_{1}^{L})=f(a_{1}^{-L}w)=0$ for every
clean word $w$.

#####

Now, suppose that there exists a clean word $w$ such that
$f(a_{1}^{-L}wa_{1}^{L})=c\neq 0$. Then let us take the word

$v=wa_{1}^{L}a_{2}a_{1}^{-L}.$

For this word $v^{k}=wa_{1}^{L}a_{2}a_{1}^{-L}wa_{1}^{L}a_{2}a_{1}^{-L}\ldots
wa_{1}^{L}a_{2}a_{1}^{-L}$. Since $x_{a_{1}^{k}}=0$ for any $k\in\mathbb{Z}$
and $x_{a_{2}}=0$, it is clear that

$f(v^{k})=f(wa_{1}^{L})+f(a_{1}^{L}a_{2}a_{1}^{-L})+\sum_{i=1}^{k-1}(f(a_{1}^{-L}wa_{1}^{L})+f(a_{1}^{L}a_{2}a_{1}^{-L}))=$
$f(wa_{1}^{L})+f(a_{2})+\sum_{i=1}^{k-1}(f(a_{1}^{-L}wa_{1}^{L})+f(a_{2}))=0+0+\sum_{i=1}^{k-1}(c+0)=c(k-1).$

Therefore if $f$ is bounded, then $f(a_{1}^{-L}wa_{1}^{L})=0$ for every clean
word $w$.

#####

Now, let $f$ still be bounded, and suppose there exists a clean word $w$ such
that $f(w)\neq 0$. In this case, if we take the word

$v=wa_{1}^{L}wa_{1}^{-L},$

then for this word $v^{k}=wa_{1}^{L}wa_{1}^{-L}wa_{1}^{L}wa_{1}^{-L}\ldots
wa_{1}^{L}wa_{1}^{-L}$, and similarly to the previous case

$f(v^{k})=f(wa_{1}^{L})+f(w)+\sum_{i=1}^{k-1}(f(a_{1}^{-L}wa_{1}^{L})+f(w))=0+f(w)+\sum_{i=1}^{k-1}(0+f(w))=kf(w),$

thus $f$ is still unbounded. Therefore since we presume $f$ to be bounded, it
also holds that $f(w)=0$ for any clean word $w$. In particular, it follows
that $x_{s}=0$ for any $s\in\bar{S}^{1}$.

#####

Now, let $w$ be a word of smallest length such that $x_{w}\neq 0$. Since we
have presumed $f$ to be bounded, $|w|>1$. Now $f(w)=x_{w}\neq 0$, thus
$w_{1}=a_{1}^{-1}$ or $w_{fin}=a_{1}$, or both. If $w_{1}=a_{1}^{-1}$ and
$w_{fin}\neq a_{1}$, then let $w^{\prime}=a_{2}w$. If $w_{1}\neq a_{1}^{-1}$
and $w_{fin}=a_{1}$, then let $w^{\prime}=wa_{2}^{-1}$. Finally, if
$w_{1}=a_{1}^{-1}$ and $w_{fin}=a_{1}$, then let
$w^{\prime}=a_{2}wa_{2}^{-1}$.

#####

Now, let

$\Delta_{1}^{f}(w)=\sum_{\begin{subarray}{c}v\in
F_{n},2\leq|v|\leq|w|\end{subarray}}x_{v}\delta_{1}(v,w),$

and let

$\Delta_{fin}^{f}(w)=\sum_{\begin{subarray}{c}v\in
F_{n},2\leq|v|\leq|w|\end{subarray}}x_{v}\delta_{fin}(v,w)$

with $\delta_{1}$, $\delta_{fin}$ defined in 1.9. These functions represent
restrictions of $f$ to counting subwords of length at least $2$ that $w$
starts with (respectively, ends with). Now note that if $w_{1}=a_{1}^{-1}$,
then $w^{\prime}$ starts with $a_{2}a_{1}^{-1}$ and thus
$\Delta_{1}^{f}(w^{\prime})=0$. Similarly, if $w_{fin}=a_{1}$, it holds that
$\Delta_{fin}^{f}(w^{\prime})=0$

#####

In the first case of $w^{\prime}$ the function value $f(w^{\prime})$ can be
represented as

$f(w^{\prime})=f(a_{2}w)=f(w)+f(a_{2})+\Delta_{1}^{f}(w^{\prime})=f(w)+0+0=f(w)\neq
0.$

In the second case

$f(w^{\prime})=f(wa_{2}^{-1})=f(w)+f(a_{2}^{-1})+\Delta_{fin}^{f}(w^{\prime})=f(w)+0+0=f(w)\neq
0.$

Finally, in the third case

$f(w^{\prime})=f(a_{2}wa_{2}^{-1})=f(w)+(f(a_{2})+\Delta_{1}^{f}(w^{\prime}))+(f(a_{2}^{-1})+\Delta_{fin}^{f}(w^{\prime}))-x_{w^{\prime}}=$
$f(w)+0+0-0=f(w)\neq 0,$

with the last term included due to the fact that $w^{\prime}$ itself is
counted in both $\Delta_{1}^{f}(w^{\prime})$ and
$\Delta_{fin}^{f}(w^{\prime})$. In all three equations the second step follows
from the fact that $f(a_{2})=f(a_{2}^{-1})=0$ and that $x_{v}=0$ for any word
$v$ that starts with $a_{2}a_{1}^{-1}$ or ends with $a_{1}a_{2}^{-1}$.
However, in all three cases $w^{\prime}$ is a clean word, thus $f(w^{\prime})$
must be equal to $0$. Thus we have arrived at a contradiction and $f$ can not
be bounded. ∎

###  3.3 Brooks space

######  Lemma 3.5.

The set $B_{Br}$ is linearly independent.

###### Proof.

Let
$f=\sum_{i=0}^{m}x_{i}\phi_{w_{i}}=\sum_{i=0}^{m}x_{i}p_{w_{i}}-\sum_{i=0}^{m}x_{i}p_{w_{i}^{-1}}$
be some non-trivial linear combination of quasimorphisms for words $w_{i}\in
W_{Br}$. It holds that if $w_{i}\neq a_{1},a_{1}^{-1},a_{2},a_{2}^{-1}$, then
both $p_{w_{i}}$ and $p_{w_{i}^{-1}}$ lie in $\bar{B}$. Therefore
$f=x\phi_{a_{1}}+x^{\prime}\phi_{a_{2}}+f^{\prime}$, where $f^{\prime}$ is a
linear combination of elements of $\bar{B}$. If $x=x^{\prime}=0$, then
$f^{\prime}$ must be non-trivial, thus $f$ is not bounded by Lemma 3.2. If
$x\neq 0$, then $f(a_{1}^{k})=xk$, and thus $f$ is again not bounded.

#####

Now, let $x=0$ and $x^{\prime}\neq 0$, i. e.
$f=x^{\prime}\phi_{a_{2}}+f^{\prime}$, where $f^{\prime}$ is either trivial,
or not bounded. Similarly to the group case, let us presume $f$ to be bounded
and take the word

$v=a_{2}a_{1}^{L}a_{2}a_{1}^{-L}.$

Similarly to the group case proof,

$f(v^{k})=f(a_{2}a_{1}^{L})+f(a_{2})+(k-1)(f(a_{1}^{-L}a_{2}a_{1}^{L})+f(a_{2})),$

therefore $f(a_{1}^{-L}a_{2}a_{1}^{L})=-f(a_{2})=-x^{\prime}\neq 0$. On the
other hand, $f(a_{2})=-f(a_{2}^{-1})$, since $f$ consists of quasimorphisms,
therefore $f(a_{1}^{-L}a_{2}a_{1}^{L})=f(a_{2}^{-1})$. Now let

$v^{\prime}=a_{2}a_{1}^{L}a_{2}^{-1}a_{1}^{-L}.$

Again,

$f(v^{\prime
k})=f(a_{2}a_{1}^{L})+f(a_{2}^{-1})+(k-1)(f(a_{1}^{-L}a_{2}a_{1}^{L})+f(a_{2}^{-1}))=$
$f(a_{2}a_{1}^{L})+f(a_{2}^{-1})+2(k-1)f(a_{2}^{-1}),$

and since $f(a_{2}^{-1})\neq 0$, it follows that $f$ can not be bounded. ∎

##  4 Proof conclusions

###### Proof (Theorem 1.5).

From Lemma 2.1 it follows that the set $B$ spans $\widehat{C}(M_{n})$, and
from Lemma 3.1 it follows that $B$ is linearly independent, thus it is a basis
of $\widehat{C}(M_{n})$. Similarly, from Lemma 2.2 it follows that the set
$\bar{B}$ spans $\widehat{C}(F_{n})$, and from Lemma 3.2 it follows that
$\bar{B}$ is linearly independent, thus it is a basis of $\widehat{C}(F_{n})$.
Finally, from Lemma 2.4 it follows that the set $B_{Br}$ spans
$\widehat{Br}(F_{n})$, and from Lemma 3.5 it follows that $B_{Br}$ is linearly
independent, thus it is a basis of $\widehat{Br}(F_{n})$ ∎

The proof of Theorem 1.4 can be easily derived from the proofs given in
Section 2.

###### Proof (Theorem 1.4).

In Section 2 we have proven that any elementary counting function (and
therefore any counting function) may be represented as

$\sum_{i=0}^{m}x_{i}p_{w_{i}}+\sum_{j=0}^{m^{\prime}}y_{j}l_{v_{j}}+\sum_{k=0}^{m^{\prime\prime}}z_{k}r_{u_{k}}$

with $p_{w_{i}}\in B$ (respectively $\bar{B}$) being basis elements, and
$l_{v_{j}}$ and $r_{u_{k}}$ being left and right extension relations for some
words. Therefore any two counting functions that lie in the same equivalency
class with respect to the relation $\sim$ differ by a linear combination of
left and right extension relations, thus $l_{w}$ and $r_{w}$ span $K$, which
concludes the proof for the monoid and group cases.

#####

Finally, for the Brooks space let us prove that for $\sigma_{1}$ and
$\sigma_{2}$ from (2) it stands that the functions $s_{w}$ span
$\operatorname{Ker}\sigma_{1}$ and the functions $se_{w}$ span
$\sigma_{1}^{-1}(\operatorname{Ker}\sigma_{2})$. Since
$\sigma_{1}(p_{w})=p_{w}-p_{w}^{-1}$, it is clear that
$\operatorname{Ker}\sigma_{1}$ is exactly the set of all symmetric counting
functions, thus it is spanned by $p_{w}+p_{w^{-1}}=s_{w}$. Next, from the same
proofs in Section 2 it follows that any linear combination of Brooks
quasimorphisms can be represented in the following form:

$\sum_{i=0}^{m^{\prime\prime\prime}}x_{i}^{\prime}\phi_{w^{\prime}_{i}}=\sum_{i=0}^{m^{\prime\prime\prime}}x_{i}^{\prime}p_{w^{\prime}_{i}}-\sum_{i=0}^{m^{\prime\prime\prime}}x_{i}^{\prime}p_{w_{i}^{\prime-1}}=$
$\Bigl{(}\sum_{i=0}^{m}x_{i}p_{w_{i}}+\sum_{j=0}^{m^{\prime}}y_{j}l_{v_{j}}+\sum_{k=0}^{m^{\prime\prime}}z_{k}r_{u_{k}}\Bigr{)}-\Bigl{(}\sum_{i=0}^{m}x_{i}p_{w_{i}^{-1}}+\sum_{j=0}^{m^{\prime}}y_{j}r_{v_{j}^{-1}}+\sum_{k=0}^{m^{\prime\prime}}z_{k}l_{u_{k}^{-1}}\Bigr{)}=$
$\Bigl{(}\sum_{i=0}^{m}x_{i}p_{w_{i}}-\sum_{i=0}^{m}x_{i}p_{w_{i}^{-1}}\Bigr{)}+\sum_{j=0}^{m^{\prime}}y_{j}(l_{v_{j}}-r_{v_{j}^{-1}})-\sum_{k=0}^{m^{\prime\prime}}z_{k}(l_{u_{k}^{-1}}-r_{u_{k}})=$
$\sum_{i=0}^{m}x_{i}\phi_{w_{i}}+\sum_{j=0}^{m^{\prime}}y_{j}se_{v_{j}}-\sum_{k=0}^{m^{\prime\prime}}z_{k}se_{u_{k}^{-1}}$

with $\phi_{w_{i}}\in B_{Br}$ also being basis elements, therefore the pre-
image of $\operatorname{Ker}\sigma_{2}$ is spanned by $se_{w}$, and from (2)
it follows that $K_{Br}$ is indeed spanned by $s_{w}$ and $se_{w}$. ∎

## References

  * [1] Tobias Hartnick and Alexey Talambutsa (2018) Relations between counting functions on free groups and free monoids, Groups Geom. Dyn. 12, 1485–1521.
  * [2] Tobias Hartnick and Alexey Talambutsa, Efficient computations with counting functions on free groups and free monoids, arXiv:2109.14947 [math.GR].
  * [3] R. Brooks, Some remarks on bounded cohomology. In Riemann surfaces and related topics. (Stony Brook, 1978.) Annals of Mathematics Studies, 97. Princeton University Press, Princeton, N.Y., 1980, 53–63. Zbl 0457.55002 MR 0624804
  * [4] Y. Mitsumatsu, Bounded cohomology and ‘1 -homology of surfaces. Topology 23 (1984), no. 4, 465–471. Zbl 0568.55002 MR 0780736
  * [5] V. A. Faiziev, Pseudocharacters on free groups. Izv. Ross. Akad. Nauk Ser. Mat. 58 (1994), no. 1, 121–143, in Russian. English translation, Russian Acad. Sci. Izv. Math. 44 (1995), no. 1, 119–141. MR 1271517
  * [6] R. I. Grigorchuk, Some results on bounded cohomology. In A. Duncan, N. Gilbert, and J. Howie (eds.), Combinatorial and geometric group theory. (Edinburgh, 1993.) London Mathematical Society Lecture Note Series, 204\. Cambridge University Press, Cambridge, 1995, 111–163. Zbl 0853.20034 MR 1320279
  * [7] Antonius Hase, Dynamics of Out($F_{n}$) on the second bounded cohomology of $F_{n}$, arXiv:1805.00366v1 [math.GR]


# Scene Designer: a Unified Model for Scene Search and Synthesis from Sketch

Leo Sampaio Ferraz Ribeiro  ICMC, Universidade de São Paulo – São Carlos/SP,
Brazil
<EMAIL_ADDRESS>Tu Bui  CVSSP, University of Surrey
-- Guildford, Surrey, UK
<EMAIL_ADDRESS>John Collomosse  CVSSP, University of
Surrey -- Guildford, Surrey, UK
<EMAIL_ADDRESS>Adobe Research, Creative Intelligence Lab
-- San Jose, CA, USA
<EMAIL_ADDRESS>Moacir Ponti  ICMC, Universidade de São Paulo – São
Carlos/SP, Brazil
<EMAIL_ADDRESS>
###### Abstract

Scene Designer is a novel method for searching and generating images using
free-hand sketches of scene compositions; i.e. drawings that describe both the
appearance and relative positions of objects. Our core contribution is a
single unified model to learn both a cross-modal search embedding for matching
sketched compositions to images, and an object embedding for layout synthesis.
We show that a graph neural network (GNN) followed by Transformer under our
novel contrastive learning setting is required to allow learning correlations
between object type, appearance and arrangement, driving a mask generation
module that synthesizes coherent scene layouts, whilst also delivering state
of the art sketch based visual search of scenes.

##  1 Introduction

Creativity is increasingly inspired by the wealth of visual content online.
Visual search eases content discovery and re-use, whilst generative artwork is
emerging as a novel genre, driven by models trained on thousands of images.
Yet the fusion of search and synthesis is under-explored. Generative content
oveoffers users control but rarely the quality and diversity of real images.
By contrast, search offers quality but not customization. Recent works have
explored both image search and generation guided by free-hand sketches; an
intuitive way to communicate visual intent. Sketch therefore offers an
opportunity to unify search and synthesis technologies within a creative
workflow.

This paper presents Scene Designer; a unified model for searching and
generating scenes using free-hand sketches of scene compositions; i.e.
drawings that describe both the appearance and relative positions of multiple
objects. Our model provides a cross-modal search embedding where similarity of
visual compositions comprising sketches and images (or mixtures of both) can
be measured, as well as an object-level embedding for the synthesis of scene
layouts to generate images. Our technical contributions are:

Figure 1: Scene Designer enables iterative design of image compositions
through retrieval and synthesis. Row 1: User sketches initial concept, and
matching scenes are returned (1). Row 2: In each column, the user uses the
search results to help compose the final image; an orange square means the
background was selected (2, 3) while the blue one means an object crop was
chosen and added to the composition (4); on the final stage the user poses the
objects as desired, and the final scene is synthesized (5).

1\. Compositional Sketch Search. We propose a hybrid graph neural network
(GNN) and Transformer architecture to learn a metric search embedding for
comparing sketched and photographic scenes. Existing sketch based image
retrieval (SBIR) methods predominantly match queries containing a single,
dominant object invariant to its position within an image. Our novel
contrastive training matches sketched compositions containing multiple
objects.

Figure 2: Proposed architecture of Scene Designer. Compositions (spatial
arrangements of sketched or photoreal objects) are encoded via (a) to produce
an object-level representation; _i.e_. a feature encoding for each object in
the scene. A scene graph is constructed from these and encoded via GNN (b) to
yield the constrained-correlated representation, and subsequently via
Transformer to produce (c) the freely-correlated representation and scene
representation. The roman numerals indicate where each of the losses (see Sec.
3.1, 3.4 and 3.5) are applied during training: (i) Cross-entropy
classification $\mathcal{L}_{CCE}$, (ii) Triplet loss $\mathcal{L}_{tri}$,
(iii) Mask generation losses $\mathcal{L}_{G_{m}}$, (iv) Bounding box
generation losses $\mathcal{L}_{G_{b}}$, (v) Contrastive loss
$\mathcal{L}_{cont}$, (vi) Final cross-entropy classification
$\mathcal{L}_{CCE_{f}}$.

2\. Sketch-to-Scene Synthesis. We hallucinate entire scene layouts from either
fully or partially sketched compositions, via a decoder that generates and
combines object masks synthesized from learned correlations between object
type, appearance and arrangement. The scene layouts drive texture synthesis to
generate photographic content.

3\. Fusion of Synthesis and Cross-Domain Search. Training a single mixed-task
model yields improvements on the state of the art for both scene search and
scene synthesis tasks. We also enable a novel creative workflow in which image
compositions may be created iteratively; users sketch an initial composition
(one or more objects), elements of the resulting images may be incorporated
potentially with further sketched objects to drive either further searches or
full image synthesis. Fig. 1 demonstrates how our fused model enables
iterative design of generative compositions.

##  2 Related Work

Sketch based image retrieval (SBIR) has received extensive attention in the
past decade. Dictionary learning methods (e.g. bag of visual words) have
leveraged wavelet, edge-let, shape-let and sparse gradient features [1, 2] to
match sketches to edge structures in images. With the advent of deep learning,
CNNs (convnets) were rapidly adopted for cross-modal representation learning;
exploring joint search embeddings for matching structure between sketches and
images. Early approaches learned mappings between edge maps and sketches using
contrastive [3], siamese [4] and triplet networks [5]. Fine-grained SBIR was
explored by Yu _et al_. [6] and Sangkloy _et al_. [7] who used a three-branch
CNN with triplet loss. Bui _et al_. learned a cross-domain embedding through
triplet loss and partial weight sharing between sketch-image encoders [8].
Later studies followed a natural extension from single object sketches to
scenes with multiple objects. Liu _et al_. [9] recently used a graph encoder
with triplet loss to do compositional SBIR, but their results were dependent
on known bounding boxes and category labels of photos and sketches. Our method
also explores sketched compositions for search, learning a GNN and Transformer
hybrid model for both search and synthesis.

Conditional Image Generation has been a rapidly developing field since the
introduction of Conditional GANs [10]. Initial work exploring class label
priors were soon followed by models with image based priors such as Pix2Pix
[11] and more recently high definition synthesis models such as Pix2PixHD [12]
and SPADE [13]. Those models learn from pairs of matching samples from each
domain, and are capable of mapping semantic layouts to images.

Scene Graphs are a representation for images where individual objects are
defined as nodes with the graph edges describe their relationships. They were
first used for text-based image retrieval [14] but were more recently used by
Johnson _et al_. [15] and Ashual _et al_. [16] as a initial representations to
drive semantic layout generation and image synthesis based on those layouts.
Our synthesis approach follows a similar principle, where our model learns to
generate semantic layouts and a separate GAN (SPADE [13]) synthesizes the
final image.

Image-synthesis from Sketch is a challenging problem due to the abstract and
ambiguous nature of sketches. Recent work such as Sketchy-GAN [17] and
ContextualGAN [18] achieved promising results generating images from single-
object sketches, but as was shown in [19], cannot accommodate sketched scenes
with multiple objects. Gao _et al_. [19] were the first to implement image
synthesis from sketch scenes and introduced the paired SketchyCOCO dataset.
Our approach differs, in that we learn a single mixed-task model for both
search and synthesis --- improving quantitatively and in user study synthesis
results.

Joint image search and synthesis has been largely unexplored. Early work
includes Sketch2Photo [20] that supports image search using text and sketch
queries then compose an output image from objects of interest found in the
returned results. This approach uses statistical methods for image composition
thus does not yield high quality output. In a more recent work, Sketchformer
[21] also supports search and synthesis but only for sketch (single-domain).
Similarly, Pang _et al_. [22] uses a sketch decoder mainly to assist their
cross-domain learning thus have poor synthesized results. Our method learns
both a cross-domain embedding for scene sketches and images and also enables
image synthesis from composed objects in either domains.

##  3 Methodology

We developed a cross-modal representation learning framework in order to
represent images and sketches with multiple objects in a common feature space;
this representation is useful to both cross-modal retrieval and generation.
Making use of scene graph representations, our framework looks at objects in a
scene using a hierarchy based on object correlation. Fig. 2 describes the
architecture and stages of the representation, which are each summarized
below:

  1. 1.

Object-level representation (OLR): Given an input composition, we encode
individual objects (which might be sketched or photo-real) to a common
representation. We refer to this embedding, in which each object is
independently represented, as the OLR (subsec. 3.1).

  2. 2.

Scene Graph (SG): is formed using the OLR to encode objects, along with the
discrete positional relationships of all object pairs.

  3. 3.

Constrained-correlated representation (CCR): A graph neural network (GNN)
encodes nodes in the Scene Graph (SG) into a continuous representation,
encoding object appearances and their pairwise correlations (subsec. 3.2).

  4. 4.

Freely-correlated representation (FCR): The sets of correlated vectors are fed
into a Transformer module, where the attention layers allow for free
correlation between all objects. The FCR encodes relationships between each
object and all other objects in a weighted manner (subsec. 3.3). This
representation is used for synthesis (subsec. 3.4).

  5. 5.

Scene representation (SR): Together with the FCR, the Transformer module
computes a separate single-vector latent space to which metric learning is
applied to train a search embedding (subsec. 3.5).

We now describe in further detail how each stage of the representation is
learned.

###  3.1 Object-level Representation (OLR)

We begin by independently encoding each object within the input composition to
a common feature embedding, regardless of its input modality. Following
contemporary single-object SBIR [8, 7, 6] we adopt a deep metric learning
approach using a heterogeneous triplet architecture (_i.e_. no shared weights
between the anchor (a) and positive/negative (p/n) branches). Our network
comprises a MobileNet [23] backbone, terminated with two shared fully
connected (fc) layers, the latter yielding the 128-D OLR embedding.

The MobileNet is pre-trained on ImageNet [24], and finetuned for cross-domain
learning using a combined categorical cross-entropy (CCE) and triplet loss,
with the latter defined as:

$\begin{split}\mathcal{L}_{tri}\left(a,p,n\right)=\max\\{0,m&+|f_{s}(a),f_{i}(p)|_{2}\\\
&-|f_{s}(a),f_{i}(n)|_{2}\\}\end{split}$ (1)

where $f_{s}(.)$ is the MobileNet that encodes sketches, $f_{i}(.)$ the one
that encodes photo-real objects cropped from images, each followed by shared-
domain MLP (2 fc layers) that encodes the MobileNet‘s outputs to the OLR,
$m=0.5$ is the margin and $|.|_{2}$ is the $L_{2}$ norm. Hereafter, we use
shorthand $f(.)$ to refer to the encoder irrespective of its modality. The OLR
is trained using rasterized sketches (a), and objects cropped from the COCO-
stuff dataset with corresponding (p) and differing (n) object class; see
subsec. 4.1 for dataset details. To aid convergence, the equal-weighted CCE
loss $CCE(.)$ is applied to a further fc layer $f_{e}(.)$ appended to the
network: vspace-0.4em

$\displaystyle\mathcal{L}_{cce}(a,p,n)$ $\displaystyle=$
$\displaystyle\sum_{c\in\\{a,p,n\\}}CCE(f_{e}(c),\hat{c}))$ (2)

where $\hat{a}$,$\hat{p}$, $\hat{n}$ are the one-hot vectors encoding the
semantic class of each input.

###  3.2 Constrained-Correlated Representation (CCR)

A scene graph (SG) describes objects and their spatial relationships within
the composition. Formally an SG is a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ where
$\mathcal{V}=\\{o_{1},\cdots,o_{i},\cdots,o_{\kappa}\\}$ is set of nodes
representing the $\kappa$ objects, and $(o_{i},r_{ij},o_{j})\in\mathcal{E}$
the set of edges encoding discrete relationships, $r_{ij}\in\mathcal{R}$ (we
used ‘‘left of’’, ‘‘right of’’, ‘‘above’’, ‘‘below’’, ‘‘contains’’, ‘‘inside
of’’).

We encode the scene graph via a graph neural network (GNN). We represent each
node via the OLR as $f(o_{i})$, encoding the pose and appearance of the
object. As in [16], we adopt a learnable embedding $f_{r}(r_{ij})$ to map
relationships $\mathcal{R}$ into dense vectors. The GNN $g_{r}(.)$ comprises a
sequence of 6 layers $g_{r}^{k}(.)$. In each we follow the architecture of
[15], and edges are processed by an fc layer $f_{fc1}^{k}$:

$\begin{split}<v_{i}^{0},r_{ij}^{0},v_{j}^{0}>&=<f(o_{i}),f_{r}(r_{ij}),f(o_{j})>\\\
<\hat{v}_{i}^{k},r_{ij}^{k+1},\hat{v_{j}}^{k}>&=f_{fc1}^{k}(<v_{i}^{k},r_{ij}^{k},v_{j}^{k}>)\end{split}$
(3)

that updates the vector for each relationship to $r_{ij}^{k+1}$ and builds the
set $\hat{v}_{i}^{k}\in V^{k}$ of object vectors. A function ($h$) gathers
vectors in $\mathcal{V}$ that describe the same object and averages them;
finally they are processed by another fc layer to compute the updated
$v_{i}^{k+1}=f_{fc2}^{k}(h(V^{k}))$ for each object. These layers are shared
between images and sketches and trained end-to-end as part of our model to
learn the constrained-correlated representation (CCR).

###  3.3 Freely-Correlated Representation (FCR) and Scene Representation (SR)

We require a final representation that allows for objects to learn from their
connection to all others in the scene, without being constrained to the
pairwise encoding of the SG. We model this via attention layers, stacked
similarly to a Transformer architecture [25]. This approach was inspired by
the use of LSTMs for SG representation in [26] in order to accommodate a
variable number of objects within a single representation. Transformers offer
an attention mechanism to analyze each vector against all others, making them
a good candidate for our model; They employ positional encoding so that the
sequence order information is kept during processing. Our objects do not have
a defined order, but we want their spacial positions to be taken into account.
Following [16], we break the scene into a 5x5 grid and attribute a position
$p\in{0,1,...,24}$ to each object based on where its center falls on the grid.
This $p$ is used to compute its positional encoding (see Fig. 3). Note that
Ashual _et al_. concatenated this $p$ to the object embeddings processed by
the GNN; we took our approach because the vectors processed by our GNN are
dynamic and because it aligns better with the Transformer architecture.

We specify our Transformer $t(.)=Z$ with 3 layers, and 16 attention heads on
each. The input is the CCR $g_{r}(f(o_{i}))$ for each object in the image and
one empty vector $\vec{0}$. In each layer $t^{i}(.)$ the model computes the
attention weights that relate each vector to all the vectors in the sequence:

$\begin{split}Z^{0}&=s\left(F_{q}^{0}(Q+E)F_{k}^{0}(Q+E)^{T}\right)F_{v}^{0}(Q+E)\\\
Z^{i+1}&=s\left(F_{q}^{i}(Z^{i})F_{k}^{i}(Z^{i})^{T}\right)F_{v}^{i}(Z^{i}),\end{split}$
(4)

where multiplications are matrix-based, $s$ is the softmax function,
$F_{q}^{i}$, $F_{k}^{i}$, $F_{v}^{i}$ are fc layers, $Q$ is a matrix made by
stacking $\vec{0}$ and $g_{r}(f(o_{i}))$ CCR vectors and $E$ is our positional
encodings $f_{p}(p)$, stacked in the same fashion as $Q$. In the output, the
position that contained $\vec{0}$ has the SR while the other ones contain the
FCR for each object.

Figure 3: Grid-based Positional Encoding. We adapted the positional encoder
from traditional Transformers by attributing one encoding to each block of the
gridded scene.

###  3.4 Semantic Layout Generation

The learned FCR is used to synthesize a semantic scene layout (c.f. Fig. 7)
that is used by our image generator. The layout is made from bounding boxes
and masks for each object. We train two generators, one for masks and one for
bounding boxes. The box generator is trained using Generalized Intersection-
over-Union (GIOU) [27] and mean-squared error (MSE). The generator itself is a
2-layer MLP. The mask generator is trained within a GAN [28] framework, using
a conditional setup [10] with LSGAN [29] losses plus MSE and Feature Matching
to regularize the adversarial training. Additionally, another CCE
classification loss $\mathcal{L}_{CCE_{f}}$ is applied to the FCR to encourage
it to remain semantic.

Taking $b$ as ground truth bounding box, $\hat{x}_{i}$ as the FCR based on
image input and $\hat{x}_{s}$ as the FCR based on sketch input, our generation
losses are, for bounding boxes:

$\mathcal{L}_{G_{b}}(x)=\lambda_{1}\mathcal{L}_{GIOU}(b,G_{b}(\hat{x}))+\lambda_{2}|b,G_{b}(\hat{x})|_{2}$
(5)

for each object on each image, applied to both $\hat{x}_{i}$ and
$\hat{x}_{s}$, with $\lambda_{1}=\lambda_{2}=10$. Using a similar notation,
take our ground truth masks as $m_{g}$, and the object labels as $y\in C$,
where $C$ is the set of object classes. The loss for the mask generator is:

$\begin{split}\mathcal{L}_{G_{m}}(\hat{x})&=\lambda_{3}|m_{g},G_{m}(x)|_{2}+\lambda_{4}|D(G_{m}(\hat{x}),y),1|_{2}\\\
&+\lambda_{5}\mathcal{L}_{FM}(\hat{D}(m_{g},y),\hat{D}(G_{m}(x),y))\end{split}$
(6)

with $D$ as the discriminator and also applied to both $\hat{x}_{i}$ and
$\hat{x}_{s}$. The weights are $\lambda_{3}=10$, $\lambda_{4}=0.25$,
$\lambda_{5}=10$. The $\mathcal{L}_{FM}(.)$ is the feature matching loss, the
L1 difference in the activations of $D$ ($\hat{D}(.)$). $D$ itself is trained
with the adversarial loss in classic GAN fashion. Those losses back-propagate
through all representation levels.

Finally, we turn the masks and boxes into a semantic layout. In this object-
only layout, objects are placed ordered by their size, so that bigger objects
are behind smaller ones (after [16]); then it may be combined with a layout
for the background (_e.g_. selected from the top search results or coarsely
drawn). Ultimately the final layout is passed through a SotA SPADE model [13]
to synthesize an image.

###  3.5 Compositional Sketch-based Image Retrieval

For scene retrieval, we learn a single Scene Representation (SR) as a search
embedding in which the similarity of images and the sketched input may be
measured. This is an additional latent vector computed by the Transformer,
that has metric properties encouraged through an adaptation of the contrastive
loss.

Figure 4: During contrastive training of the SR, negatives are synthesized by
swapping objects in the scene for others of differing class. This helps the
model prioritize class over structure. First column shows the original image,
the second the individual cropped objects, and the third the swapped objects.

During contrastive training, we sample half of our negatives randomly from
other images of scenes in the training set. The other half of the negatives
are synthesized by swapping objects of different class into the positions of
the objects in the positive image (Fig. 4). By including such a class-swapped
version of the image as a negative, the model is encouraged to discriminate
change in object class to a greater degree than changes in object positions.
Our contrastive loss, adapted to incorporate these synthetic negatives, is:

$\begin{split}\mathcal{L}_{cont}(x_{s},x_{i},x_{sn})&=\dfrac{1}{2}(Y)(\mathcal{D}(x_{s},x_{i}))\\\
&+\dfrac{1}{4}(1-Y)(1-\mathcal{D}(x_{s},x_{i}))\\\
&-\dfrac{1}{4}\mathcal{D}(x_{s},x_{sn}),\end{split}$ (7)

where $\mathcal{D}$ computes $|.|_{2}$ between all vectors on one set and all
vectors on another set, $x_{s}$ and $x_{i}$ are respectively the sketch-based
and image-based SR, $Y$ is a label indicating if a pair of vectors are from
the same scene. Finally, $x_{sn}$ is the SR of the synthesized scenes with
swapped objects.

###  3.6 Training Stages

Training is performed in three stages. First the OLR is trained independent of
the rest of the model, using the dual triplet and categorical cross-entropy
loss, for 100K iterations, on single-object sketches and object crops. In the
second stage we use our novel soft-paired sketch and image scenes dataset (see
Sec. 4.1) to train entire model end-to-end for a further 120K iterations.
Finally, we finetune the model with a hard-paired dataset, training for a
further 5K iterations. Training is via the ADAM [30] optimizer, with
$\beta_{1}=0.5$ and $\epsilon=1e-9$; learning rate (lr) is $lr=10^{-4}$ for
the first two stages and $lr=10^{-5}$ for the finetuning stage. The mask
discriminator follows the Two Time-Scale Update Rule (TTUR) [31] with
$lr_{D}=4lr$.

##  4 Experiments and Discussion

We evaluate the performance of Scene Designer for both compositional sketch
search (SBIR) and synthesis, contrasting performance against contemporary
baselines for both tasks. We explore the efficacy of our model for both search
and synthesis from sketch, image and mixed domain compositions. For SBIR we
compare against four baselines: a scene-level technique (SceneSketcher [9])
and three single-object techniques. Of these, two are fine-grained SBIR models
(Sketchy [7], and Sketch-me-that-shoe [6]), and one is coarse-grained (Multi-
stage Learning or MSL [8]). For scene synthesis we compare against the sketch
driven method of Gao _et al_. [19] (proposed alongside their SketchyCOCO
dataset) and the method of Ashual _et al_. [16] that accepts semantic scene
graphs (spatial arrangements of keywords) as input.

###  4.1 Datasets

We require paired data; sketched compositions and corresponding images of the
scenes depicted by those sketches.

SketchyCOCO is a recent dataset of 14K such pairs, proposed for sketch based
scene synthesis [19]. SketchyCOCO samples scenes and associated annotations
(bounding boxes, masks) from the COCO-stuff [32] images dataset, augmenting
these with sketched depictions of those scenes. Approximately 4K of
SketchyCOCO images contain object instances (the remainder are solely
background material; ‘stuff’). Only 14 classes (14c) of objects are annotated.
To mitigate overfitting, we use the SketchyCOCO training partition (4,060
samples) only for fine-tuning our model. We include the test partition in our
evaluation and split it per experiment requirements: retrieval eval. uses 233
samples as [9] needs scenes with 2 or more objects; generation tests needs to
use the overlap between test sets used in each of the compared models: 137
samples. We also emulate [9] in constructing an ‘Extended SketchyCOCO’ search
corpus by holding out 5K random images from the COCO-stuff training set and
adding these to the SketchyCOCO test set as distractors.

QuickDrawCOCO-92c is a novel dataset we propose, composing scenes with
sketches from QuickDraw, the largest public sketch dataset (50M) [33].
Inspired by SketchyCOCO, we similarly leverage scenes from COCO-stuff, taking
advantage of the class overlap (92c) with QuickDraw. We synthesize sketch
scenes by compositing sketches from QuickDraw onto a canvas, selecting a
random sketch within the class corresponding to each object in a COCO-stuff
image (Fig. 5). Our dataset is soft-paired, in that the sketches for each
object do not necessarily match pose and appearance with the image, only the
class label. We use QuickDrawCOCO-92c for all training stages except for the
final finetuning stage where we combine samples from both SketchyCOCO and
QuickDrawCOCO-92c. We separately fuse the training and test partitions of the
QuickDraw and COCO-stuff datasets to partition QuickDrawCOCO-92c into 111,112
training, 2,788 test and 1,907 validation scenes. This dataset is 6x more
category-diverse and has 8x more samples than SketchyCOCO.

Figure 5: Sample paired data from the proposed QuickDrawCOCO-92c dataset. Each
row shows one COCO-stuff [32] image and three examples of synthetic sketched
compositions matching that image derived from QuickDraw [33].

###  4.2 Evaluating Retrieval

Figure 6: Retrieval results using the QuickDrawCOCO (first block) and
SketchyCOCO sets (second). The results often contain the exact match and are
contextually consistent, such as in the last row of QuickDrawCOCO, where the
context of ‘‘table-spoon-mug-etc’’ retrieves sets of ‘‘meals’’. Relevant
results in green; final row of each block represents a failure case.

We adopt the evaluation proposed in SceneSketcher [9], the only prior
technique exploring SBIR for scenes; retrieved images are relevant only if
they match the sketched scene exactly. Models are evaluated on SketchyCOCO,
QuickDrawCOCO-92c and ‘Extended SketchyCOCO’.

Compositional search. Tab. 1 reports recall at rank $k=\\{1,5,10\\}$ (R@k) for
our proposed search embedding for sketched scenes, that of SceneSketcher [9],
and three single-object SBIR baselines: Sketch-me-that-shoe [6]; Sketchy [7];
and MSL [8]. We report R@k over SketchyCOCO and Extended SketchyCOCO for all
methods; figures for SceneSketcher and Sketch-me-that-shoe are taken from Liu
_et al_. [9]. We are unable to report values for these two models over our
QuickDrawCOCO-92c test data, due to the lack of public models/code for these
methods. QuickDrawCOCO-92c is a more challenging query set due to its
increased size and the more messy / abstract sketches within QuickDraw. We
present our results alongside public Sketchy [7] and MSL [8] models (final
column, Tab. 1).

Our model more than doubles previous SotA recall results and greatly improves
other metrics. The penultimate row of Tab. 1 reports performance our method
using mixed-domain queries, where we substitute half of the sketched objects
for their image cropped counterparts, which yields an even higher result
likely due to half of the objects sharing the same domain as the test corpus.
The final row reports on our model trained on QuickDrawCOCO-92c only; prior to
finetuning on SketchyCOCO training set. This demonstrates that our model
generalizes sufficiently to beat the SotA on SketchyCOCO without explicit
training on it. Visual results for both datasets are in Fig. 6.

Single object search. We evaluate the performance of our model at single-
object retrieval, baselining against both the Sketchy and MSL models on the
SketchyCOCO dataset. We sample 120 queries randomly from SketchyCOCO
containing only one object. In contrast to composition search, many relevant
results exist in the SketchyCOCO dataset for a given sketched object. We
consider a result relevant if both its category and pose match the sketched
query. Since no ground-truth annotation with these criteria is available for
SketchyCOCO, we crowd-source per-query annotation via Mechanical Turk (MTurk)
for the top-$k$ ($k$=15) results and compute both recall@$k$ and precision@$k$
in Tab. 2. For each ranked result we ask 5 MTurk participants to indicate
relevance (or not), and filter on consensus level. Our approach significantly
outperforms both baselines at all consensus levels. The sensitivity to object
orientation and pose underlines the utility of sketch over labeled boxes (per
[16]) to specify the appearance of the desired object.

Method | SketchyCOCO | Ext. SCOCO | QuickDrawCOCO
---|---|---|---
r@1 | r@5 | r@10 | r@1 | r@5 | r@10 | r@1 | r@5 | r@10
Ours | 75.53 | 96.56 | 99.14 | 66.09 | 90.55 | 96.13 | 62.15 | 78.90 | 85.07
Sketch-me-that-shoe [6] | 06.19 | 17.15 | 32.86 | <0.01 | <0.01 | 01.90 | - | - | -
Sketchy [7] | 03.43 | 09.87 | 15.87 | <0.01 | 00.85 | 00.85 | 00.07 | 00.35 | 00.60
MSL [8] | 09.44 | 28.75 | 43.34 | 05.15 | 15.87 | 17.59 | 00.10 | 00.53 | 01.07
SceneSketcher [9] | 31.91 | 66.67 | 86.19 | 12.38 | 26.67 | 38.10 | - | - | -
Ours (Mixed-domain) | 89.69 | 99.57 | 100.0 | 87.12 | 96.56 | 98.71 | 93.22 | 97.37 | 98.23
Ours (Before finetuning) | 45.49 | 80.25 | 93.56 | 15.45 | 41.20 | 50.21 | 64.27 | 81.95 | 87.23
Table 1: Recall@K metrics on the SketchyCOCO dataset, its extended version and
the QuickDrawCOCO-92c set. Our model more than doubles the previous state-of-
the-art recall@1 metric. Additionally, we show our performance when using
mixed-domain compositions and also with the model trained only with
QuickDrawCOCO-92c, before finetuning on SketchyCOCO.

Method Precision@1 Precision@15 C2 C3 C4 C2 C3 C4 Ours 66.12 52.07 37.19 22.98
16.14 10.30 MSL [8] 16.53 14.05 09.09 10.41 07.00 04.41 Sketchy [7] 35.54
23.97 18.18 17.36 11.79 07.77 Recall@1 Recall@15 C2 C3 C4 C2 C3 C4 Ours 66.12
52.07 37.19 96.69 90.91 71.90 MSL [8] 16.53 14.05 09.09 84.30 72.73 56.20
Sketchy [7] 35.54 23.97 18.18 85.95 80.17 65.29

Table 2: MTurk sketch search results for the proposed and baseline methods on
the SketchyCOCO dataset. Precision@k and Recall@k are presented at different
(C)oncensus thresholds.

###  4.3 Evaluating Scene Synthesis

We evaluate the performance of our proposed model at image synthesis (see
Fig.8) using SketchyCOCO, comparing against that dataset’s accompanying public
model [19], and against the public model of Ashual _et al_. [16] which
synthesizes images from spatial word maps _i.e_. implicit scene graphs. We
synthesize from the sketch, and use the paired image as ground truth for
evaluating the fidelity of the output. For Ashual _et al_., we create an input
scene graph based on object classes and bounding boxes.

Figure 7: Example layouts synthesized by Scene Designer before they are
transformed to images by the SPADE [13] generator. First 2 columns show
SketchyCOCO scenes and third column shows QuickDrawCOCO-92c scenes.

Objective Metrics. We compute Fréchet Inception Distance (FID) [31] and Object
Classification Accuracy [16] to compare the synthesized and ground truth
images. A lower FID value indicates that the tested image distribution is
closer the original and is more realistic. The Accuracy values come from
finetuning a ResNet-101 classifier on crops from COCO and applying it to
foreground objects cropped from the generated images.

Tab. 4 shows our model to score higher than both baselines on both FID and
Accuracy. We have included results applying SPADE to the ground-truth layout,
which serves as an upper bound generation result for our method. Results from
mixed-domain and images-only compositions, which are a unique capability of
our model, are also included. These show the value in applying Scene Designer
to incrementally build up a composition as part of an interactive creative
process.

User Perceptual Study. We assess the quality of our synthesized images
following the subjective evaluation methodology proposed by Gao _et al_. [19].
Specifically we score how ‘realistic’ each image is, and how ‘faithful’ each
synthesized image is in representing the spatial object arrangement of the
input scene (in the case of [16], spatial arrangement of labeled boxes). User
opinion on ‘faithfulness’ is scored on a scale 1 (‘very dissatisfied’) to 4
(‘very satisfied’) using crowd-sourced annotations collected via MTurk. For
realism, images synthesized by each method are presented to participants,
inviting selection of the most realistic. In both cases each task is annotated
by 4 unique participants, and results tabulated for differing levels of
participant consensus. We consider only results where 2 or more MTurkers agree
_i.e_. there was consensus. Tab. 3 indicates our method is preferred for
content faithfulness and realism, although faithfulness scores are low in
general (circa 2.5 on the scale) this is in line with reported figures for
other methods e.g. 1.57 for [16] as shown in [19].

Figure 8: Generating images with Scene Designer. The first 3 rows show compositions and sketches from SketchyCOCO whilst the last one shows those from QuickDrawCOCO-92c. There are three features shown: (a) sketch composition. (b) compositions that mix image and sketched objects. (c) individual object posing, where we flipped each object individually and compare the generations. Method | SketchyCOCO | QuickDrawCOCO
---|---|---
Realism | Faithfulness | Realism | Faithfulness
C2 | C3 | C4 | C2 | C3 | C4 | C2 | C3 | C4 | C2 | C3 | C4
Ours | 64.17 | 72.73 | 82.61 | 2.67 | 2.50 | 2.16 | 62.77 | 63.64 | 75.68 | 2.66 | 2.56 | 2.58
Ashual _et al_. [16] | 13.33 | 13.64 | 04.35 | 2.56 | 2.34 | 1.90 | 37.23 | 36.36 | 24.32 | 2.61 | 2.58 | 2.88
SketchyCOCO [19] | 22.50 | 13.64 | 13.04 | 2.79 | 2.65 | 2.04 | - | - | - | - | - | -
Table 3: User perceptual study (via MTurk) evaluating the generated images.
Realness is a comparative score between the models while faithfulness is
individually scored per method on continuous scale [1,4]. Results are
thresholded for different levels of participant (C)onsensus, from 2 to 4 (out
of 4) participant agreements.

Method SketchyCOCO QDCOCO-92c FID$\downarrow$ Acc.$\uparrow$ FID$\downarrow$
Acc.$\uparrow$ Ours (sketch-based) 130.87 63.46 76.64 65.47 Ashual _et al_.
[16] 170.40 56.20 103.14 50.69 SketchyCOCO [19] 198.17 29.14 - - Ours (image-
based) 138.82 57.36 69.08 59.52 Ours (mixed-domain) 143.24 65.74 83.13 58.53
SPADE [13] 111.25 81.21 58.39 80.95

Table 4: Generation metrics when using samples from SketchyCOCO and
QuickDrawCOCO-92c. Both quantitative metrics were computed on the overlapping
test set across the three/two models for each dataset (137 samples on the
former and 1300 on the later). A lower FID and higher Object Classification
Accuracy represent a better result. We’ve also included the metrics for the
SPADE generator, representing an upper bound for our model.

###  4.4 Ablation studies

Model Settings | r@1 | r@10 |  FID$\downarrow$
---|---|---|---
(A1) W/o Transformer | 07.20 | 20.62 | 102.79
(A2) W/o GNN | 02.69 | 17.61 | 118.04
(A3) W/o positional encoding | 14.45 | 45.87 | 122.01
(B1) W/o obj.-level pretraining | 55.84 | 85.43 | 102.14
(B2) W/o synthesized negatives | 54.12 | 81.16 | 128.58
(C1) No contrastive loss | 45.48 | 74.67 | 129.88
(C2) No generation losses | 55.84 | 81.34 | 129.98
Final model | 62.15 | 85.07 | 76.64
Table 5: Ablation Studies, showing Recall@k and FID on QuickDrawCOCO. With
each set of models, we want to show that (A) each component is necessary, (B)
the training procedure aids performance and (C) the single model can multi-
task well.

We explore the significance of each stage of our proposed architecture and
training methodology, comparing SBIR and generation results on
QuickDrawCOCO-92c using several ablated variants as shown in Tab. 5, alongside
the QuickDrawCOCO-92c result for the full method. We explore three categories
of ablation (A-C). Category A ablates key features of the proposed
architecture. Category B ablates key training steps. Category C investigates
if training a single model for both search and synthesis does not degrade the
model’s performance at either.

(A1) Without Transformer.  Removes the attention modules from the model,
aggregating the representations from the GNN using simple addition.

(A2) Without GNN.  Substitutes the GNN for an fc layer that bridges the OLR
into the Transformer module.

(A3) Without Positional Encoding.  Retains the proposed architecture but
removes our grid-based positional encoding from the Transformer module.

(B1) Without object-level pretraining.  Skips the first stage of training the
OLR.

(B2) Without shuffled-objects negatives.  Does not use our synthesized
negative samples in the contrastive loss.

(C1) No Contrastive Loss.  Does not use contrastive loss. The results on this
model are driven by the masks and boxes generation losses and object-level
triplet loss only.

(C2) No Generation Losses.  By removing the masks and boxes generation losses,
this ablated model is only trained with search associated losses.

Removing either the GNN (A2) or the grid-based positional encoding (A3)
degrades both tasks’ performance significantly while the Transformer (A1) is
shown to be helpful for generation (improves FID by 25%), and crucial for
search.

Our synthesized negative examples (B2) improve search by 8% and are essential
for generation to work. This follows the result of (C1) where removing the
Contrastive Loss also diminishes generation performance; given that both of
those are associated with search but also impact generation show that the
strength of our multi-task model lies on the synergy between those tasks.

When we then look at (C2) that hypothesis is further proven, as removing the
synthesis-related losses impact the search results as well with a drop of 6%
in recall@1. Training for both tasks does not decrease performance, but boosts
it meaningfully. We conclude that learning general representations requires
the model to retain both visual and semantic information, which we achieve by
mixing generation and feature learning losses.

##  5 Conclusion

We introduced Scene Designer; a single unified model for searching and
generating images using free-hand sketches of scenes. We developed a mixed-
task learning framework with three levels of representation (OLR, CCR, FCR)
using a hybrid GNN-Transformer architecture. Scene Designer learns to embed
sketched and photographic scenes into a common space, producing latent
representations for both synthesizing layouts from sketched scenes and for
measuring compositional similarity between sketch and image scenes. The model
is trained via an expanded dataset of sketch compositions and corresponding
images (QuickDrawCOCO-92c); a secondary contribution of our work. We show that
the combination of feature learning and generation losses aided by our novel
take on contrastive learning for scenes are responsible for obtaining SotA
performance at scene search and synthesis tasks. The ability to sketch an
initial composition, and incorporate components of results into hybrid queries
for synthesis (or further searches) creates a novel mechanism for
interactively constructing scenes from digital image collections. Further work
could explore this interactive model in creative practice, and perhaps explore
how other facets of generative artwork (_e.g_. neural style transfer) might be
incorporated into the framework for example to enable fine-grained control
over the appearance of objects within the composition.

## Acknowledgments

This work was supported by FAPESP (grants 2017/22366-8, 2019/02808-1,
2019/07316-0), CNPq Fellowship (304266/2020-5), and a charitable donation from
Adobe Inc.

## References

  * [1] Mathias Eitz, Kristian Hildebrand, Tamy Boubekeur, and Marc Alexa.  Sketch-based image retrieval: Benchmark and bag-of-features descriptors.  IEEE Trans. Visualization and Computer Graphics, 17(11):1624--1636, 2011.
  * [2] Rui Hu and John Collomosse.  A performance evaluation of gradient field hog descriptor for sketch based image retrieval.  Computer Vision and Image Understanding, 117(7):790--806, 2013.
  * [3] Fang Wang, Le Kang, and Yi Li.  Sketch-based 3d shape retrieval using convolutional neural networks.  In Computer Vision and Pattern Recognition (CVPR), 2015 IEEE Conference on, pages 1875--1883. IEEE, 2015.
  * [4] Yonggang Qi, Yi-Zhe Song, Honggang Zhang, and Jun Liu.  Sketch-based image retrieval via siamese convolutional neural network.  In Image Processing (ICIP), 2016 IEEE International Conference on, pages 2460--2464. IEEE, 2016.
  * [5] Tu Bui, Leo Ribeiro, Moacir Ponti, and John Collomosse.  Compact descriptors for sketch-based image retrieval using a triplet loss convolutional neural network.  Computer Vision and Image Understanding, 2017.
  * [6] Qian Yu, Feng Liu, Yi-Zhe Song, Tao Xiang, Timothy M Hospedales, and Chen-Change Loy.  Sketch me that shoe.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 799--807, 2016.
  * [7] Patsorn Sangkloy, Nathan Burnell, Cusuh Ham, and James Hays.  The sketchy database: learning to retrieve badly drawn bunnies.  ACM Transactions on Graphics (TOG), 35(4):119, 2016.
  * [8] Tu Bui, Leo Ribeiro, Moacir Ponti, and John Collomosse.  Sketching out the details: Sketch-based image retrieval using convolutional neural networks with multi-stage regression.  Computers & Graphics, 71:77--87, 2018.
  * [9] Fang Liu, Changqing Zou, Xiaoming Deng, Ran Zuo, Yu-Kun Lai, Cuixia Ma, Yong-Jin Liu, and Hongan Wang.  Scenesketcher: Fine-grained image retrieval with scene sketches.  2020\.
  * [10] Mehdi Mirza and Simon Osindero.  Conditional generative adversarial nets.  arXiv preprint arXiv:1411.1784, 2014.
  * [11] P. Isola, J. Zhu, T. Zhou, and A. A. Efros.  Image-to-image translation with conditional adversarial networks.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5967--5976, 2017.
  * [12] Ting-Chun Wang, Ming-Yu Liu, Jun-Yan Zhu, Andrew Tao, Jan Kautz, and Bryan Catanzaro.  High-resolution image synthesis and semantic manipulation with conditional gans.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018.
  * [13] Taesung Park, Ming-Yu Liu, Ting-Chun Wang, and Jun-Yan Zhu.  Semantic image synthesis with spatially-adaptive normalization.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
  * [14] Justin Johnson, Ranjay Krishna, Michael Stark, Li Jia Li, David A. Shamma, Michael S. Bernstein, and Fei Fei Li.  Image retrieval using scene graphs.  In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, volume 07-12-June, pages 3668--3678. IEEE, jun 2015.
  * [15] Justin Johnson, Agrim Gupta, and Li Fei-Fei.  Image Generation from Scene Graphs.  In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1219--1228. IEEE, jun 2018.
  * [16] Oron Ashual and Lior Wolf.  Specifying object attributes and relations in interactive scene generation.  In Proceedings of the IEEE International Conference on Computer Vision, volume 2019-Octob, pages 4560--4568, sep 2019.
  * [17] Wengling Chen and James Hays.  Sketchygan: Towards diverse and realistic sketch to image synthesis.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [18] Yongyi Lu, Shangzhe Wu, Yu-Wing Tai, and Chi-Keung Tang.  Image generation from sketch constraint using contextual gan.  In The European Conference on Computer Vision (ECCV), September 2018\.
  * [19] Chengying Gao, Qi Liu, Qi Xu, Limin Wang, Jianzhuang Liu, and Changqing Zou.  Sketchycoco: Image generation from freehand scene sketches.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [20] Tao Chen, Ming-Ming Cheng, Ping Tan, Ariel Shamir, and Shi-Min Hu.  Sketch2photo: Internet image montage.  Proc. ACM SIGGRAPH, 28(5):124, 2009.
  * [21] Leo Sampaio Ferraz Ribeiro, Tu Bui, John Collomosse, and Moacir Ponti.  Sketchformer: Transformer-based representation for sketched structure.  In Proc. CVPR, 2020.
  * [22] Kaiyue Pang, Yi-Zhe Song, Tony Xiang, and Timothy M Hospedales.  Cross-domain generative learning for fine-grained sketch-based image retrieval.  In BMVC, pages 1--12, 2017.
  * [23] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  arXiv preprint arXiv:1704.04861, 2017.
  * [24] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  ImageNet Large Scale Visual Recognition Challenge.  International Journal of Computer Vision (IJCV), 115(3):211--252, 2015.
  * [25] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 5998--6008. Curran Associates, Inc., 2017.
  * [26] Longteng Guo, Jing Liu, Jinhui Tang, Jiangwei Li, Wei Luo, and Hanqing Lu.  Aligning linguistic words and visual semantic units for image captioning.  In Laurent Amsaleg, Benoit Huet, Martha A. Larson, Guillaume Gravier, Hayley Hung, Chong-Wah Ngo, and Wei Tsang Ooi, editors, Proceedings of the 27th ACM International Conference on Multimedia, MM 2019, Nice, France, October 21-25, 2019, pages 765--773. ACM, 2019.
  * [27] Hamid Rezatofighi, Nathan Tsoi, JunYoung Gwak, Amir Sadeghian, Ian Reid, and Silvio Savarese.  Generalized intersection over union: A metric and a loss for bounding box regression.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [28] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In Advances in Neural Information Processing Systems 27, 2014.
  * [29] Xudong Mao, Qing Li, Haoran Xie, Raymond Y. K. Lau, and Zhen Wang.  Least squares generative adversarial networks, 2016.  cite arxiv:1611.04076.
  * [30] Diederik Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In 3rd International Conference on Learning Representations (ICLR), 2015.
  * [31] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 6629–6640, Red Hook, NY, USA, 2017. Curran Associates Inc.
  * [32] Holger Caesar, Jasper Uijlings, and Vittorio Ferrari.  Coco-stuff: Thing and stuff classes in context.  In Computer vision and pattern recognition (CVPR), 2018 IEEE conference on. IEEE, 2018.
  * [33] The Quick, Draw! Dataset.  https://github.com/googlecreativelab/quickdraw-dataset, 2018.  Accessed: 2018-10-11.