figurec

# Trajeglish: Learning the Language of Driving Scenarios

Jonah Philion1,2,3, Xue Bin Peng1,4, Sanja Fidler1,2,3
1NVIDIA, 2University of Toronto, 3Vector Institute, 4Simon Fraser University
{jphilion, japeng<EMAIL_ADDRESS>
###### Abstract

A longstanding challenge for self-driving development is simulating dynamic
driving scenarios seeded from recorded driving logs. In pursuit of this
functionality, we apply tools from discrete sequence modeling to model how
vehicles, pedestrians and cyclists interact in driving scenarios. Using a
simple data-driven tokenization scheme, we discretize trajectories to
centimeter-level resolution using a small vocabulary. We then model the multi-
agent sequence of motion tokens with a GPT-like encoder-decoder that is
autoregressive in time and takes into account intra-timestep interaction
between agents. Scenarios sampled from our model exhibit state-of-the-art
realism; our model tops the Waymo Sim Agents Benchmark, surpassing prior work
along the realism meta metric by 3.3% and along the interaction metric by
9.9%. We ablate our modeling choices in full autonomy and partial autonomy
settings, and show that the representations learned by our model can quickly
be adapted to improve performance on nuScenes. We additionally evaluate the
scalability of our model with respect to parameter count and dataset size, and
use density estimates from our model to quantify the saliency of context
length and intra-timestep interaction for the traffic modeling task.

##  1 Introduction

In the short term, self-driving vehicles will be deployed on roadways that are
largely populated by human drivers. For these early self-driving vehicles to
share the road safely, it is imperative that they become fluent in the ways
people interpret and respond to motion. A failure on the part of a self-
driving vehicle to predict the intentions of people can lead to overconfident
or overly cautious planning. A failure on the part of a self-driving vehicle
to communicate to people its own intentions can endanger other roadusers by
surprising them with uncommon maneuvers.

In this work, we propose an autoregressive model of the motion of roadusers
that can be used to simulate how humans might react if a self-driving system
were to choose a given sequence of actions. At test time, as visualized in
Fig. 1, the model functions as a policy, outputting a categorical distribution
over the set of possible states an agent might move to at each timestep.
Iteratively sampling actions from the model results in diverse, scene-
consistent multi-agent rollouts of arbitrary length. We call our approach
“Trajeglish” due to the fact that we model multi-agent trajectories as a
sequence of discrete tokens, similar to the representation used in language
modeling, and to make an analogy between how roadusers use vehicle motion to
communicate and how people use verbal languages, like English, to communicate.

A selection of samples from our model is visualized in Fig. 2. When generating
these samples, the model is prompted with only the initial position and
heading of the agents, in contrast to prior work that generally requires at
least one second of historical motion to begin sampling. Our model generates
diverse outcomes for each scenario, while maintaining the scene-consistency of
the trajectories. We encourage readers to consult our project page for videos
of scenarios sampled from our model in full control and partial control
settings, as well as longer rollouts of length 20 seconds.

Our main contributions are:

  * •

A simple data-driven method for tokenizing trajectory data we call “k-disks”
that enables us to tokenize the Waymo Open Dataset (WOMD) (Ettinger et al.,
2021) at an expected discretization error of 1 cm using a small vocabulary
size of 384.

  * •

A transformer-based architecture for modeling sequences of motion tokens that
conditions on map information and one or more initial states per agent. Our
model outputs a distribution over actions for agents one at a time which we
show is ideal for interactive applications.

  * •

State-of-the-art quantitative and qualitative results when sampling rollouts
given real-world initializations both when the traffic model controls all
agents in the scene as well as when the model must interact with agents
outside its control.

We additionally evaluate the scalability of our model with respect to
parameter count and dataset size, visualize the representations learned by our
model, and use density estimates from our model to quantify the extent to
which intra-timestep dependence exists between agents, as well as to measure
the relative importance of long context lengths for traffic modeling (see Sec.
4.3).

###  1.1 Related Work

Our work builds heavily on recent work in imitative traffic modeling. The full
family of generative models have been applied to this problem, including VAEs
(Suo et al., 2021; Rempe et al., 2021), GANs (Igl et al., 2022), and diffusion
models (Zhong et al., 2022; Jiang et al., 2023). While these approaches
primarily focus on modeling the multi-agent joint distribution over future
trajectories, our focus in this work is additionally on building reactivity
into the generative model, for which the factorization provided by
autoregression is well-suited. For the structure of our encoder-decoder, we
draw inspiration from Scene Transformer (Ngiam et al., 2021) which also uses a
global coordinate frame to encode multi-agent interaction, but does not
tokenize data and instead trains their model with a masked regression
strategy. A limitation of regression is that it’s unclear if the Gaussian or
Laplace mixture distribution is flexible enough to represent the distribution
over the next state, whereas with tokenization, we know that all scenarios in
WOMD are within the scope of our model, the only challenge is learning the
correct logits. A comparison can also be made to the behavior cloning
baselines used in Symphony (Igl et al., 2022) and “Imitation Is Not Enough”
(Lu et al., 2023) which also predict a categorical distribution over future
states, except our models are trained directly on pre-tokenized trajectories
as input, and through the use of the transformer decoder, each embedding
receives supervision for predicting the next token as well as all future
tokens for all agents in the scene. In terms of tackling the problem of
modeling complicated continuous distributions by tokenizing and applying
autoregression, our work is most similar to Trajectory Transformer (Janner et
al., 2021) which applies a fixed-grid tokenization strategy to model state-
action sequences for RL. Finally, our work parallels MotionLM (Seff et al.,
2023) which is concurrent work that also uses discrete sequence modeling for
motion prediction, but targets 1- and 2-agent online interaction prediction
inistead of $N$-agent offline closed-loop simulation.

Figure 1: Inputs and outputs At a given timestep, our model predicts a
distribution over a fixed set of $V$ states defined relative to an agent’s
current location and heading, and conditions on map information, actions from
all previous timesteps (green), and any actions that have already been chosen
by other agents within the current timestep (blue). We model motion of all
agents relevant to driving scenarios, including vehicles, pedestrians, and
cyclists.

Figure 2: Trajeglish Visualizations of samples from our model. Rollouts within
each row are given the same single-timestep initialization, outlined in black.
Future trajectories become lighter for timesteps farther into the future.
While some tracks overlap in the figure, they do not overlap when time is
taken into account; there are no collisions in these rollouts. Videos are
available on our project page.

##  2 Imitative Traffic Modeling

In this section, we show that the requirement that traffic models must
interact with all agents at each timestep of simulation, independent of the
method used to control each of the agents, imposes certain structural
constraints on how the multi-agent future trajectory distribution is factored
by imitative traffic models. Similar motivation is provided to justify the
conditions for submissions to the WOMD sim agents benchmark to be considered
valid closed-loop policies (Montali et al., 2023).

We are given an initial scene with $N$ agents, where a scene consists of map
information, the dimensions and object class for each of the $N$ agents, and
the location and heading for each of the agents for some number of timesteps
in the past. For convenience, we denote information about the scene provided
at initialization by $\bm{c}$. We denote the state of a vehicle $i$ at future
timestep $t$ by ${\bm{s}}_{t}^{i}\equiv(x^{i}_{t},y^{i}_{t},h^{i}_{t})$ where
$(x,y)$ is the center of the agent’s bounding box and $h$ is the heading. For
a scenario of length $T$ timesteps, the distribution of interest for traffic
modeling is given by

$\displaystyle
p(\bm{s}_{1}^{1},...,\bm{s}_{1}^{N},\bm{s}_{2}^{1},...,\bm{s}_{2}^{N},...,\bm{s}_{T}^{1},...,\bm{s}_{T}^{N}\mid\bm{c}).$
(1)

We refer to samples from this distribution as rollouts. In traffic modeling,
our goal is to sample rollouts under the restriction that at each timestep, a
black-box autonomous vehicle (AV) system chooses a state for a subset of the
agents. We refer to the agents controlled by the traffic model as “non-player
characters” or NPCs. This interaction model imposes the following
factorization of the joint likelihood expressed in Eq. 1

$\displaystyle\begin{split}&p(\bm{s}_{1}^{1},...,\bm{s}_{1}^{N},\bm{s}_{2}^{1},...,\bm{s}_{2}^{N},...,\bm{s}_{T}^{1},...,\bm{s}_{T}^{N}\mid\bm{c})\\\
&=\prod_{1\leq t\leq
T}p(\bm{s}_{t}^{1...N_{0}}|\bm{c},\bm{s}_{1...t-1})\underbrace{p(\bm{s}^{N_{0}+1...N}_{t}\mid\bm{c},\bm{s}_{1...t-1},\bm{s}_{t}^{1...N_{0}})}_{\text{NPCs}}\end{split}$
(2)

where
$\bm{s}_{1...t-1}\equiv\\{\bm{s}_{1}^{1},\bm{s}_{1}^{2},...,\bm{s}_{t-1}^{N}\\}$
is the set of all states for all agents prior to timestep $t$,
$\bm{s}^{1...N_{0}}_{t}\equiv\\{\bm{s}_{t}^{1},...,\bm{s}_{t}^{N}\\}$ is the
set of states for agents 1 through $N$ at time $t$, and we arbitrarily
assigned the agents out of the traffic model’s control to have indices
$1,...,N_{0}$. The factorization in Eq. LABEL:eq:factor shows that we seek a
model from which we can sample an agent’s next state conditional on all states
sampled in previous timesteps as well as any states already sampled at the
current timestep.

We note that, although the real-world system that generated the driving data
involves independent actors, it may still be important to model the influence
of actions chosen by other agents at the same timestep, a point we expand on
in Appendix A.1. While intra-timestep interaction between agents is weak in
general, explicitly modeling this interaction provides a window into
understanding cases when it is important to consider for the purposes of
traffic modeling.

##  3 Method

In this section, we introduce Trajeglish, an autoregressive generative model
of dynamic driving scenarios. Trajeglish consists of two components. The first
component is a strategy for discretizing, or “tokenizing” driving scenarios
such that we model exactly the conditional distributions required by the
factorization of the joint likelihood in Eq. LABEL:eq:factor. The second
component is an autoregressive transformer-based architecture for modeling the
distribution of tokenized scenarios.

Important features of Trajeglish include that it preserves the dynamic
factorization of the full likelihood for dynamic test-time interaction, it
accounts for intra-timestep coupling across agents, and it enables both
efficient sampling of scenarios as well as density estimates. While sampling
is the primary objective for traffic modeling, we show in Sec. 4.3 that the
density estimates from Trajeglish are useful for understanding the importance
of longer context lengths and intra-timestep dependence. We introduce our
tokenization strategy in Sec. 3.1 and our autoregressive model in Sec. 3.2.

Figure 3: Tokenization We iteratively find the token with minimum corner
distance to the next state. An example trajectory is shown in green. The raw
representation of the tokenized trajectory is shown as boxes with blue
outlines. States that have yet to be tokenized are light green. Token
templates are optimized to minimize the error between the tokenized
trajectories and the raw trajectories. Figure 4: Raw motion token
representation We plot the raw representation of action sets extracted with
k-disks for $|V|\in\\{128,256,384,512\\}$. Agents sample one of these actions
at each timestep. Figure 5: Token frequency We plot the frequency that each
token appears in the validation and training sets. Note that we sort the
tokens by their frequency for each class individually for the ID. Increasing
the vocabulary size increases the resolution but also results in a longer
tail. The distribution of actions on the training set and validation set match
closely.

###  3.1 Tokenization

The goal of tokenization is to model the support of a continuous distribution
as a set of $|V|$ discrete options. Given ${\bm{x}}\in\mathbb{R}^{n}\sim
p({\bm{x}})$, a tokenizer is a function that maps samples from the continuous
distribution to one of the discrete options $f:\mathbb{R}^{n}\rightarrow V$. A
renderer is a function that maps the discrete options back to raw input
$r:V\rightarrow\mathbb{R}^{n}$. A high-quality tokenizer-renderer pair is one
such that $r(f(\bm{x}))\approx\bm{x}$. The continuous distributions that we
seek to tokenize for the case of traffic modeling are given by Eq. 1. We note
that these distributions are over single-agent states consisting of only a
position and heading. Given the low dimensionality of the input data, we
propose a simple approach for tokenizing trajectories based on a fixed set of
state-to-state transitions.

Figure 6: K-means vs. k-disks We plot the average discretization error for
multiple template sets sampled from k-means and k-disks with $|V|=384$. Alg. 1
consistently samples better template sets than k-means.

#### Method

Let ${\bm{s}}_{0}$ be the state of an agent with length $l$ and width $w$ at
the current timestep. Let ${\bm{s}}$ be the state at the next timestep that we
seek to tokenize. We define $V=\\{\bm{s}_{i}\\}$ to be a set of template
actions, each of which represents a change in position and heading in the
coordinate frame of the most recent state. We use the notation
$a_{i}\in\mathbb{N}$ to indicate the index representation of token template
$\bm{s}_{i}$ and $\hat{\bm{s}}$ to represent the raw representation of the
tokenized state $\bm{s}$. Our tokenizer $f$ and renderer $r$ are defined by

$\displaystyle
f({\bm{s}}_{0},{\bm{s}})=a_{i^{*}}=\operatorname*{arg\,min}_{i}d_{l,w}({\bm{s}}_{i},\mathrm{local}({\bm{s}}_{0},{\bm{s}}))$
(3) $\displaystyle
r({\bm{s}}_{0},a_{i})=\hat{{\bm{s}}}=\mathrm{global}({\bm{s}}_{0},{\bm{s}}_{i})$
(4)

where $d_{l,w}({\bm{s}}_{0},{\bm{s}}_{1})$ is the average of the L2 distances
between the ordered corners of the bounding boxes defined by ${\bm{s}}_{0}$
and ${\bm{s}}_{1}$, “local” converts ${\bm{s}}$ to the local frame of
${\bm{s}}_{0}$, and “global” converts ${\bm{s}}_{i^{*}}$ to the global frame
out of the local frame of ${\bm{s}}_{0}$. We use $d_{l,w}(\cdot,\cdot)$
throughout the rest of the paper to refer to this mean corner distance metric.
Importantly, in order to tokenize a full trajectory, this process of
converting states ${\bm{s}}$ to their tokenized counterpart $\hat{{\bm{s}}}$
is done iteratively along the trajectory, using tokenized states as the base
state ${\bm{s}}_{0}$ in the next tokenization step. We visualize the procedure
for tokenizing a trajectory in Fig. 3. Tokens generated with our approach have
three convenient properties for the purposes of traffic modeling: they are
invariant across coordinate frames, invariant under temporal shift, and they
supply efficient access to a measure of similarity between tokens, namely the
distance between the raw representations. We discuss how to exploit the third
property for data augmentation in Sec. A.2.

#### Optimizing template sets

We propose an easily parallelizable approach for finding template sets with
low discretization error. We collect a large number of state transitions
observed in data, sample one of them, filter transitions that are within
$\epsilon$ meters, and repeat $|V|$ times. Pseudocode for this algorithm is
included in Alg. 1. We call this method for sampling candidate templates
“k-disks” given it’s similarity to k-means++, the standard algorithm for
seeding the anchors k-means (Arthur & Vassilvitskii, 2007), as well as the
Poisson disk sampling algorithm (Cook, 1986). We visualize the template sets
found using k-disks with minimum discretization error in Fig. 4. We verify in
Fig. 5 that the tokenized action distribution is similar on WOMD train and
validation despite the fact that the templates are optimized on the training
set. We show in Fig. 6 that the discretization error induced by templates
sampled with k-disks is in general much better than that of k-means, across
agent types. A comprehensive evaluation of k-disks in comparison to baselines
is in Sec. A.3.

Figure 7: Trajeglish modeling We train an encoder-decoder transformer that
predicts the action token of an agent conditional on previous action tokens,
map information, and agent information available at $t=0$. The diagram
represents the forward pass of the network during training in which $t=0$
agent information, map objects, and motion tokens are passed into the network
using a causal mask and the model is trained to predict the next motion token,
shown in the top right.

###  3.2 Modeling

The second component of our method is an architecture for learning a
distribution over the sequences of tokens output by the first. Our model
follows an encoder-decoder structure very similar to those used for LLMs
(Vaswani et al., 2017; Radford et al., 2019; Raffel et al., 2019). A diagram
of the model is shown in Fig. 7. Two important properties of our encoder are
that it is not equivariant to choice of global coordinate frame and it is not
permutation equivariant to agent order. For the first property, randomizing
the choice of coordinate frame during training is straightforward, and sharing
a global coordinate frame enables shared processing and representation
learning across agents. For the second property, permutation equivariance is
not actually desirable in our case since the agent order encodes the order in
which agents select actions within a timestep; the ability of our model to
predict actions should improve when the already-chosen actions of other agents
are provided.

#### Encoder

Our model takes as input two modalities that encode the initial scene. The
first is the initial state of the agents in the scene which includes the
length, width, initial position, initial heading, and object class. We apply a
single layer MLP to encode these values per-agent to an embedding of size $C$.
We then add a positional embedding that encodes the agent’s order as well as
agent identity across the action sequence. The second modality is the map. We
use the WOMD representation of a map as a collection of “map objects”, where a
map object might be a variable-length polyline representing a lane, a
sidewalk, a crosswalk, etc.. We apply a VectorNet encoder to encode the map to
a sequence of embeddings for at most $M$ map objects (Gao et al., 2020). Note
that although the model is not permutation equivariant to the agents, it is
permutation invariant to the ordering of the map objects. Similar to Wayformer
(Nayakanti et al., 2022), we then apply a layer of latent query attention that
outputs a final encoding of the scene initialization.

#### Decoder

Given the set of multi-agent future trajectories, we tokenize the trajectories
and flatten using the same order used to apply positional embeddings to the
$t=0$ agent encoder to get a sequence $a_{0}^{0}a_{1}^{0}...a_{N}^{T}$. We
then prepend a start token and pop the last token, and use an embedding table
to encode the result. For timesteps for which an agent’s state wasn’t observed
in the data, we set the embedding to zeros. We pass the full sequence through
a transformer with causal mask during training. Finally, we use a linear layer
to decode a distribution over the $|V|$ template states and train to maximize
the probability of the next token with cross-entropy loss. We tie the token
embedding matrix to the weight of the final linear layer, which we observed
results in small improvements (Press & Wolf, 2017). We leverage flash
attention (Dao et al., 2022) which we find greatly speeds up training time, as
documented in Sec. A.7.

We highlight that although the model is trained to predict the next token, it
is incorrect to say that a given embedding for the motion token of a given
agent only receives supervision signal for the task of predicting the next
token. Since the embeddings for later tokens attend to the embeddings of
earlier tokens, the embedding at a given timestep receives signal for the task
of predicting all future tokens across all agents.

##  4 Experiments

We use the Waymo Open Motion Dataset (WOMD) to evaluate trajeglish in full and
partial control environments. We report results for rollouts produced by
Trajeglish on the official WOMD Sim Agents Benchmark in Sec. 4.1. We then
ablate our design choices in simplified full and partial control settings in
Sec. 4.2. Finally, we analyze the representations learned by our model and the
density estimates it provides in Sec. 4.3. The hyperparameters for each of the
models that we train can be found in Sec. A.4.

Table 1: WOMD Sim Agents Test

Method Realism meta metric $\uparrow$ Kinematic metrics $\uparrow$ Interactive
metrics $\uparrow$ Map-based metrics $\uparrow$ minADE (m) $\downarrow$
Constant Velocity 0.2380 0.0465 0.3372 0.3680 7.924 Wayformer (Identical)
0.4250 0.3120 0.4482 0.5620 2.498 MTR+++ 0.4697 0.3597 0.4929 0.6028 1.682
Wayformer (Diverse) 0.4720 0.3613 0.4935 0.6077 1.694 Joint-Multipath++ 0.4888
0.4073 0.4991 0.6018 2.052 MTR_E* 0.4911 0.4180 0.4905 0.6073 1.656 MVTA
0.5091 0.4175 0.5186 0.6374 1.870 MVTE* 0.5168 0.4202 0.5289 0.6486 1.677
Trajeglish 0.5339 0.4019 0.5811 0.6667 1.872

###  4.1 WOMD Sim Agents Benchmark

We test the sampling performance of our model using the WOMD Sim Agents
Benchmark and report results in Tab. 1. Submissions to this benchmark are
required to submit 32 rollouts of length 8 seconds at 10hz per scenario, each
of which contains up to 128 agents. We bold multiple submissions if they are
within 1% of each other, as in Montali et al. (2023). Trajeglish is the top
submission along the leaderboard meta metric, outperforming several well-
established motion prediction models including Wayformer, MultiPath++, and MTR
(Shi et al., 2022; 2023), while being the first submission to use discrete
sequence modeling. Most of the improvement is due to the fact that Trajeglish
models interaction between agents significantly better than prior work,
increasing the state-of-the-art along interaction metrics by 9.9%. A full
description of how we sample from the model for this benchmark with
comparisons on the WOMD validation set is included in Appendix A.5.

Figure 8: Partial control ADE Left shows the ADE for the vehicles selected for
evaluation under partial control, but for rollouts where the agents are fully
autonomous. Right shows the ADE for the same vehicles but with all other
agents on replay. When agents controlled by Trajeglish go first in the
permutation order, they behave similarly to the no intra model. When they go
last, utilize the intra-timestep information to produce interaction more
similar to recorded logs, achieving a lower ADE.

###  4.2 Ablation

To simplify our ablation study, we test models in this section on the
scenarios they train on, of at most 24 agents and 6.4 seconds in length. We
compare performance across 5 variants of our model. Both “trajeglish” and
“trajeglish w/ reg.” refer to our model, the latter using the noisy
tokenization strategy discussed in Sec. A.2. The “no intra” model is an
important baseline designed to mimic the behavior of behavior cloning
baselines used in Symphony (Igl et al., 2022) and “Imitation Is Not Enough”
(Lu et al., 2023). For this baseline, we keep the same architecture but adjust
the masking strategy in the decoder to not attend to actions already chosen
for the current timestep. The “marginal” baseline is designed to mimic the
behavior of models such as Wayformer (Nayakanti et al., 2022) and MultiPath++
(Varadarajan et al., 2021) that are trained to model the distribution over
single agent trajectories instead of multi-agent scene-consistent
trajectories. For this baseline, we keep the same architecture but apply a
mask to the decoder that enforces that the model can only attend to previous
actions chosen by the current agent. Our final baseline is the same as the
marginal baseline but without a map encoder. We use this baseline to
understand the extent to which the models rely on the map for traffic
modeling.

#### Partial control

We report results in Fig. 8 in a partial controllability setting in which a
single agent in each scenario is chosen to be controlled by the traffic model
and all other agents are set to replay. The single-agent ADE (average distance
error) for the controlled-agent is similar in full autonomy rollouts for all
models other than the model that does not condition on the map, as expected.
However, in rollouts where all other agents are placed on replay, the replay
trajectories leak information about the trajectory that the controlled-agent
took in the data, and as a result, the no-intra and trajeglish rollouts have a
lower ADE. Additionally, the trajeglish rollouts in which the controlled-agent
is placed first do not condition on intra-timestep information and therefore
behave identically to the no-intra baseline, whereas rollouts where the
controlled-agent is placed last in the order provide the model with more
information about the replay trajectories and result in a decreased ADE.

#### Full control

We evaluate the collision rate of models under full control in Fig. 9 as a
function of initial context, object category, and rollout duration. The value
of modeling intra-timestep interaction is most obvious when only a single
timestep is used to seed generation, although intra-timestep modeling
significantly improves the collision rate in all cases for vehicles. For
interaction between pedestrians, Trajeglish is able to capture the grouping
behavior effectively. We observe that noising the tokens during training
improves rollout performance slightly in the full control setting. We expect
these rates to improve quickly given more training data, as suggested by Fig.
4.2.

Figure 9: Full Autonomy Collision Rate Vehicle collision rate is shown on top
and pedestrian collision rate is shown on bottom. From left to right, we seed
the scene with an increasing number of initial actions from the recorded data.
Trajeglish models the log data statistics significantly better than baselines
when seeded with only an initial timestep, as well as with longer
initialization. Figure 10: Intra-Timestep Conditioning We plot the negative
log-likelihood (NLL) when we vary how many agents choose an action before a
given agent within a given timestep. As expected, when the context length
increases, intra-timestep interaction becomes much less important to take into
account.

figureScaling Behavior Our preliminary study on parameter and dataset scaling
suggests that, compared to LLMs (Kaplan et al., 2020), Trajeglish is severely
data-constrained on WOMD; models with 35M parameters just start to be
significantly better than models with 15M parameters for datasets the size of
WOMD. A more rigorous study of how all hyperparameters of the training
strategy affect sampling performance is reserved for future work.

figurenuScenes transfer We test the ability of our model to transfer to the
maps and scenario initializations in the nuScenes dataset. The difference
between maps and behaviors found in the nuScenes dataset are such that LoRA
does not provide enough expressiveness to fine-tune the model to peak
performance. The fine-tuned models both outperform and train faster than the
model that is trained exclusively on nuScenes.

###  4.3 Analysis

#### Intra-Timestep Dependence

To understand the extent to which our model leverages intra-timestep
dependence, in Fig. 10, we evaluate the negative log likelihood under our
model of predicting an agent’s next action depending on the agent’s order in
the selected permutation, as a function of the amount of historical context
the model is provided. In all cases, the agent gains predictive power from
conditioning on the actions selected by other agents within the same timestep,
but the log likelihood levels out as more historical context is provided.
Intra-timestep dependence is significantly less important when provided over 4
timesteps of history, as is the setting used for most motion prediction
benchmarks.

#### Representation Transferability

We measure the generalization of our model to the nuScenes dataset (Caesar et
al., 2019). As recorded in Sec. A.7, nuScenes is 3 orders of magnitude smaller
than WOMD. Additionally, nuScenes includes scenes from Singapore where the
lane convention is opposite that of North America where WOMD is collected.
Nevertheless, we show in Fig. 4.2 that our model can be fine-tuned to a
validation NLL far lower than a model trained from scratch on only the
nuScenes dataset. At the same time, we find that LoRA (Hu et al., 2021) does
not provide enough expressiveness to achieve the same NLL as fine tuning the
full model. While bounding boxes have a fairly canonical definition, we note
that there are multiple arbitrary choices in the definition of map objects
that may inhibit transfer of traffic models to different datasets.

#### Token Embeddings

We visualize the embeddings that the model learns in Fig. 11. Through the task
of predicting the next token, the model learns a similarity matrix across
tokens that reflects the euclidean distance between the actions the tokens
represent.

#### Preliminary Scaling Law

We perform a preliminary study of how our model scales with increased
parameter count and dataset size in Fig. 4.2. We find that performance between
a model of 15.4M parameters and 35.6 parameters is equivalent up to 0.5B
tokens, suggesting that a huge amount of performance gain is expected if the
dataset size can be expanded beyond the 1B tokens in WOMD. We reserve more
extensive studies of model scaling for future work.

Figure 11: Token Embedding Visualization We run PCA on the model embeddings at
initialization and at convergence, and plot the $(x,y)$ location of each of
the token templates using the top 3 principal component values to determine
the hue, lightness, and saturation of the point. The model learns that tokens
that correspond to actions close together in euclidean space represent
semantically similar actions. Note that the heading of each action is not
visualized, which also affects action similarity. Additionally, the top 3
principal components include only 35% of the variance, explaining why some
colors repeat.

##  5 Conclusion

In this work, we introduce a discrete autoregressive model of the interaction
between roadusers. By improving the realism of self-driving simulators, we
hope to enhance the safety of self-driving systems as they are increasingly
deployed into the real world.

## References

  * Arthur & Vassilvitskii (2007) David Arthur and Sergei Vassilvitskii.  K-means++: The advantages of careful seeding.  In _Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’07, pp. 1027–1035, USA, 2007. Society for Industrial and Applied Mathematics.  ISBN 9780898716245.
  * Caesar et al. (2019) Holger Caesar, Varun Bankiti, Alex H. Lang, Sourabh Vora, Venice Erin Liong, Qiang Xu, Anush Krishnan, Yu Pan, Giancarlo Baldan, and Oscar Beijbom.  nuscenes: A multimodal dataset for autonomous driving.  _CoRR_ , abs/1903.11027, 2019.  URL http://arxiv.org/abs/1903.11027.
  * Cook (1986) Robert L. Cook.  Stochastic sampling in computer graphics.  _ACM Trans. Graph._ , 5(1):51–72, jan 1986.  ISSN 0730-0301.  doi: 10.1145/7529.8927.  URL https://doi.org/10.1145/7529.8927.
  * Dao et al. (2022) Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré.  Flashattention: Fast and memory-efficient exact attention with io-awareness, 2022.
  * Ettinger et al. (2021) Scott Ettinger, Shuyang Cheng, Benjamin Caine, Chenxi Liu, Hang Zhao, Sabeek Pradhan, Yuning Chai, Ben Sapp, Charles R. Qi, Yin Zhou, Zoey Yang, Aurélien Chouard, Pei Sun, Jiquan Ngiam, Vijay Vasudevan, Alexander McCauley, Jonathon Shlens, and Dragomir Anguelov.  Large scale interactive motion forecasting for autonomous driving: The waymo open motion dataset.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pp. 9710–9719, October 2021.
  * Gao et al. (2020) Jiyang Gao, Chen Sun, Hang Zhao, Yi Shen, Dragomir Anguelov, Congcong Li, and Cordelia Schmid.  Vectornet: Encoding hd maps and agent dynamics from vectorized representation, 2020.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi.  The curious case of neural text degeneration.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=rygGQyrFvH.
  * Hu et al. (2023) Anthony Hu, Lloyd Russell, Hudson Yeo, Zak Murez, George Fedoseev, Alex Kendall, Jamie Shotton, and Gianluca Corrado.  Gaia-1: A generative world model for autonomous driving, 2023.
  * Hu et al. (2021) Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, and Weizhu Chen.  Lora: Low-rank adaptation of large language models.  _CoRR_ , abs/2106.09685, 2021.  URL https://arxiv.org/abs/2106.09685.
  * Igl et al. (2022) Maximilian Igl, Daewoo Kim, Alex Kuefler, Paul Mougin, Punit Shah, Kyriacos Shiarlis, Dragomir Anguelov, Mark Palatucci, Brandyn White, and Shimon Whiteson.  Symphony: Learning realistic and diverse agents for autonomous driving simulation, 2022.
  * Janner et al. (2021) Michael Janner, Qiyang Li, and Sergey Levine.  Offline reinforcement learning as one big sequence modeling problem.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Jiang et al. (2023) Chiyu Max Jiang, Andre Cornman, Cheolho Park, Ben Sapp, Yin Zhou, and Dragomir Anguelov.  Motiondiffuser: Controllable multi-agent motion prediction using diffusion, 2023.
  * Kaplan et al. (2020) Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  _CoRR_ , abs/2001.08361, 2020.  URL https://arxiv.org/abs/2001.08361.
  * Loshchilov & Hutter (2017) Ilya Loshchilov and Frank Hutter.  Fixing weight decay regularization in adam.  _CoRR_ , abs/1711.05101, 2017.  URL http://arxiv.org/abs/1711.05101.
  * Lu et al. (2023) Yiren Lu, Justin Fu, George Tucker, Xinlei Pan, Eli Bronstein, Rebecca Roelofs, Benjamin Sapp, Brandyn White, Aleksandra Faust, Shimon Whiteson, Dragomir Anguelov, and Sergey Levine.  Imitation is not enough: Robustifying imitation with reinforcement learning for challenging driving scenarios, 2023.
  * Montali et al. (2023) Nico Montali, John Lambert, Paul Mougin, Alex Kuefler, Nick Rhinehart, Michelle Li, Cole Gulino, Tristan Emrich, Zoey Yang, Shimon Whiteson, Brandyn White, and Dragomir Anguelov.  The waymo open sim agents challenge, 2023.
  * Nayakanti et al. (2022) Nigamaa Nayakanti, Rami Al-Rfou, Aurick Zhou, Kratarth Goel, Khaled S. Refaat, and Benjamin Sapp.  Wayformer: Motion forecasting via simple and efficient attention networks, 2022.
  * Ngiam et al. (2021) Jiquan Ngiam, Benjamin Caine, Vijay Vasudevan, Zhengdong Zhang, Hao-Tien Lewis Chiang, Jeffrey Ling, Rebecca Roelofs, Alex Bewley, Chenxi Liu, Ashish Venugopal, David Weiss, Benjamin Sapp, Zhifeng Chen, and Jonathon Shlens.  Scene transformer: A unified multi-task model for behavior prediction and planning.  _CoRR_ , abs/2106.08417, 2021.  URL https://arxiv.org/abs/2106.08417.
  * Philion (2019) Jonah Philion.  Fastdraw: Addressing the long tail of lane detection by adapting a sequential prediction network.  _CoRR_ , abs/1905.04354, 2019.  URL http://arxiv.org/abs/1905.04354.
  * Press & Wolf (2017) Ofir Press and Lior Wolf.  Using the output embedding to improve language models, 2017.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language models are unsupervised multitask learners.  2019\.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _CoRR_ , abs/1910.10683, 2019.  URL http://arxiv.org/abs/1910.10683.
  * Ranzato et al. (2016) Marc’Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojciech Zaremba.  Sequence level training with recurrent neural networks.  In Yoshua Bengio and Yann LeCun (eds.), _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , 2016.  URL http://arxiv.org/abs/1511.06732.
  * Rempe et al. (2021) Davis Rempe, Jonah Philion, Leonidas J. Guibas, Sanja Fidler, and Or Litany.  Generating useful accident-prone driving scenarios via a learned traffic prior.  _CoRR_ , abs/2112.05077, 2021.  URL https://arxiv.org/abs/2112.05077.
  * Ross & Bagnell (2010) Stephane Ross and Drew Bagnell.  Efficient reductions for imitation learning.  In Yee Whye Teh and Mike Titterington (eds.), _Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics_ , volume 9 of _Proceedings of Machine Learning Research_ , pp. 661–668, Chia Laguna Resort, Sardinia, Italy, 13–15 May 2010. PMLR.  URL https://proceedings.mlr.press/v9/ross10a.html.
  * Seff et al. (2023) Ari Seff, Brian Cera, Dian Chen, Mason Ng, Aurick Zhou, Nigamaa Nayakanti, Khaled S. Refaat, Rami Al-Rfou, and Benjamin Sapp.  Motionlm: Multi-agent motion forecasting as language modeling, 2023.
  * Shi et al. (2022) Shaoshuai Shi, Li Jiang, Dengxin Dai, and Bernt Schiele.  Motion transformer with global intention localization and local movement refinement.  _Advances in Neural Information Processing Systems_ , 2022.
  * Shi et al. (2023) Shaoshuai Shi, Li Jiang, Dengxin Dai, and Bernt Schiele.  Mtr++: Multi-agent motion prediction with symmetric scene modeling and guided intention querying.  _arXiv preprint arXiv:2306.17770_ , 2023.
  * Suo et al. (2021) Simon Suo, Sebastian Regalado, Sergio Casas, and Raquel Urtasun.  Trafficsim: Learning to simulate realistic multi-agent behaviors, 2021\.
  * van den Oord et al. (2016) Aäron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew W. Senior, and Koray Kavukcuoglu.  Wavenet: A generative model for raw audio.  _CoRR_ , abs/1609.03499, 2016.  URL http://arxiv.org/abs/1609.03499.
  * Varadarajan et al. (2021) Balakrishnan Varadarajan, Ahmed Hefny, Avikalp Srivastava, Khaled S. Refaat, Nigamaa Nayakanti, Andre Cornman, Kan Chen, Bertrand Douillard, Chi-Pang Lam, Dragomir Anguelov, and Benjamin Sapp.  Multipath++: Efficient information fusion and trajectory aggregation for behavior prediction.  _CoRR_ , abs/2111.14973, 2021.  URL https://arxiv.org/abs/2111.14973.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _CoRR_ , abs/1706.03762, 2017.  URL http://arxiv.org/abs/1706.03762.
  * Zhong et al. (2022) Ziyuan Zhong, Davis Rempe, Danfei Xu, Yuxiao Chen, Sushant Veer, Tong Che, Baishakhi Ray, and Marco Pavone.  Guided conditional diffusion for controllable traffic simulation, 2022\.
  * Zhu et al. (2015) Yukun Zhu, Ryan Kiros, Richard S. Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler.  Aligning books and movies: Towards story-like visual explanations by watching movies and reading books.  _CoRR_ , abs/1506.06724, 2015.  URL http://arxiv.org/abs/1506.06724.

##  Appendix A Appendix

###  A.1 Intra-Timestep Interaction

There are a variety of reasons that intra-timestep dependence may exist in
driving log data. To list a few, driving logs are recorded at discrete
timesteps and any interaction in the real world between timesteps gives the
appearance of coordinated behavior in log data. Additionally, information that
is not generally recorded in log data, such as eye contact or turn signals,
may lead to intra-timestep dependence. Finally, the fact that log data exists
in 10-20 second chunks can result in intra-timestep dependence if there were
events before the start of the log data that result in coordination during the
recorded scenario. These factors are in general weak, but may give rise to
behavior in rare cases that is not possible to model without taking into
account coordinatation across agents within a single timestep.

###  A.2 Regularization

Trajeglish is trained with teacher forcing, meaning that it is trained on the
tokenized representation of ground-truth trajectories. However, at test time,
the model ingests its own actions. Given that the model does not model the
ground-truth distribution perfectly, there is an inevitable mismatch between
the training and test distributions that can lead to compounding errors (Ross
& Bagnell, 2010; Ranzato et al., 2016; Philion, 2019). We combat this effect
by noising the input tokens fed as input to the model. More concretely, when
tokenizing the input trajectories, instead of choosing the token with minimum
corner distance to the ground-truth state as stated in Eq. 3, we sample the
token from the distribution

$\displaystyle
a_{i}\sim\mathrm{softmax}_{i}(\mathrm{nucleus}(d(\bm{s}_{i},\bm{s})/\sigma,p_{\mathrm{top}}))$
(5)

meaning we treat the the distance between the ground-truth raw state and the
templates as logits of a categorical distribution with temperature $\sigma$
and apply nucleus sampling (Holtzman et al., 2020) to generate sequences of
motion tokens. When $\sigma=0$ and $p_{\mathrm{top}}=1$, the approach recovers
the tokenization strategy defined in Eq. 3. Intuitively, if two tokens are
equidistant from the ground-truth under the average corner distance metric,
this approach will sample one of the two tokens with equal probability during
training. Note that we retain the minimum-distance template index as the
ground-truth target even when noising the input sequence.

While this method of regularization does make the model more robust to errors
in its samples at test time, it also adds noise to the observation of the
states of other agents which can make the model less responsive to the motion
of other agents at test time. As a result, we find that this approach
primarily improves performance for the setting where all agents are controlled
by the traffic model.

Figure 12: K-disk expected discretization error Average corner distance for
each of the k-disk vocabularies of sizes 128, 256, 384, and 512. Figure 13:
Tokenization method comparison Average corner distance for trajectories
tokenized with a vocabulary of 384 with template sets derived using different
methods. Figure 14: Semantic Tokenization Performance We plot the probability
that the bounding box of an agent has non-zero overlap with another agent in
the scene for each timestep. The collision rate for the raw data is shown in
black.

###  A.3 Tokenization Analysis

We compare our approach for tokenization against two grid-based tokenizers
(van den Oord et al., 2016; Seff et al., 2023; Janner et al., 2021), and one
sampling-based tokenizer. The details of these methods are below.

$(x,y,h)$-grid \- We independently discretize change in longitudinal and
latitudinal position and change in heading, and treat the template set as the
product of these three sets. For vocabulary sizes of 128/256/384/512
respectively, we use 6/7/8/9 values for $x$ and $y$, and 4/6/7/8 values for
$h$. These values are spaced evenly between (-0.3, 3.5) m for $x$, (-0.2 m,
0.2 m) for $y$, and (-0.1, 0.1) rad for $h$.

$(x,y)$-grid \- We independenly discretize change in only the location. We
choose the heading for each template based on the heading of the state-to-
state transition found in the data with a change in location closest to the
template location. Compared to the $(x,y,h)$-grid baseline, this approach
assumes heading is deterministic given location in order to gain resolution in
location. We use 12/16/20/23 values for $x$ and $y$ with the same bounds as in
the $(x,y,h)$-grid baseline.

k-means \- We run k-means many times on a dataset of $(x,y,h)$ state-to-state
transitions. The distance metric is the distance between the $(x,y)$
locations. We note that the main source of randomness across runs is how
k-means is seeded, for which we use k-means++ Arthur & Vassilvitskii (2007).
We ultimately select the template set with minimum expected discretization
error as measured by the average corner distance.

k-disks \- As shown in Alg. 1, we sample subsets of a dataset of state-to-
state transitions that are at least $\epsilon$ from each other. For vocab
sizes of 128/256/384/512, we use $\epsilon$ of 3.5/3.5/3.5/3.0 centimeters.

Intuitively, the issue with both grid-based methods is that they distribute
templates evenly instead of focusing them in regions of the support where the
most state transitions occur. The main issue with k-means is that the heading
is not taken into account when optimizing the cluster centers.

We offer several comparisons between these methods. In Fig. 12, we plot the
expected corner distance between trajectories and tokenized trajectories as a
function of trajectory length for the template sets found with k-disks. In
Fig. 13, we compare the tokenization error as a function of trajectory length
and find that grid-based tokenizers create large oscillations. To calibrate to
a metric more relevant to the traffic modeling task, we compare the collision
rate between raw trajectories as a function of trajectory length for the raw
scenarios and the tokenized scenarios using k-disk template sets of size 128,
256, 384, and 512 in Fig. 14. We observe that a vocabulary size of 384 is
sufficient to avoid creating extraneous collisions. Finally, Fig. 15 plots the
full distribution of discretizaion errors for each of the baselines and Tab. 2
reports the expected discretization error across vocabulary sizes for each of
the methods.

Algorithm 1 Samples a candidate vocabulary of size $N$. The distance
$d(x_{0},x)$ measures the average corner distance between a box of length 1
meter and width 1 meter with state $x_{0}$ vs. state $x$.

1:procedure SampleKDisks($X$, $N$, $\epsilon$)

2: $S\leftarrow\\{\\}$

3: while len($S$) $<$ $N$ do

4: $x_{0}\sim X$

5: $X\leftarrow\\{x\in X\mid d(x_{0},x)>\epsilon\\}$

6: $S\leftarrow S\cup\\{x_{0}\\}$ return $S$

Figure 15: Discretization error distribution We plot the probability that the discretized trajectory is greater than 2 cm $\leq\epsilon\leq$ 10 cm away from the true trajectory as a function of trajectory length. Lower is therefore better. Each row visualizes the error distribution for a different method, each with a vocabulary size of 384. We keep the y-axis the same across all plots. We note that k-means discretizes more trajectories to within 2 cm than k-disks, but does not improve past 5 cm, whereas k-disks is able to tokenize nearly all trajectories in WOMD to within 6 centimeters. Table 2: Tokenization discretization error comparison |  $\mathbb{E}[d(s,\hat{s})]$ (cm)
---|---
method | $|V|=128$ | $|V|=256$ | $|V|=384$ | $|V|=512$
$(x,y,h)$-grid | 20.50 | 16.84 | 14.09 | 12.59
$(x,y)$-grid | 9.35 | 8.71 | 5.93 | 4.74
k-means | 14.49 | 8.17 | 6.13 | 5.65
k-disks | 2.66 | 1.46 | 1.18 | 1.02

###  A.4 Training hyperparameters

We train two variants of our model. The variant we use for the WOMD benchmark
is trained on scenarios with up to 24 agents within 60.0 meters of the origin,
up to 96 map objects with map points within 100.0 meters of the origin, 2 map
encoder layers, 2 transformer encoder layers, 6 transformer decoder layers, a
hidden dimension of 512, trained to predict 32 future timesteps for all
agents. We train with a batch size of 96, with a tokenization temperature of
0.008, a tokenization nucleus of 0.95, a top learning rate of 5e-4 with 500
step warmup and linear decay over 800k optimization steps with AdamW optimizer
(Loshchilov & Hutter, 2017). We use the k-disks tokenizer with vocabulary size
384. During training, we choose a random 4-second subsequence of a WOMD
scenario, a random agent state to define the coordinate frame, and a random
order in which the agents are fed to the model.

For the models we analyze in all other sections, we use the same setting from
above, but train to predict 64 timesteps, using only 700k optimization steps.
Training on these longer scenarios enables us to evaluate longer rollouts
without the complexity of extending rollouts in a fair way across models,
which we do only for the WOMD Sim Agents Benchmark and document in Sec. A.5.

###  A.5 Extended Rollouts for WOMD Sim Agents Benchmark

In order to sample scenarios for evaluation on the WOMD sim agents benchmark,
we require the ability to sample scenarios with an arbitrary number of agents
arbitrarily far from each other for an arbitrary number of future timesteps.
While it may become possible to train a high-performing model on 128-agent
scenarios on larger datasets, we found that training our model on 24-agent
scenarios and then sampling from the model using a “sliding window” (Hu et
al., 2023) both spatially and temporally achieved top performance.

In detail, at a given timestep during sampling, we determine the 24-agent
subsets with the following approach. First, we compute the 24-agent subset
associated with picking each of the agents in the scene to be the center
agent. We choose the subset associated with the agent labeled as the self-
driving car to be the first chosen subset. Among the agents not included in a
subset yet, we find which agent has a 24-agent subset associated to it with
the maximum number of agents already included in a chosen subset, and select
that agent’s subset next. We continue until all agents are included in at
least one of the subsets.

Importantly, to define the order for agents within the subset, we place any
padding at the front, followed by all agents that will have already selected
an action at the current timestep, followed by the remaining agents sorted by
distance to the center agent. In keeping this order, we enable the agents to
condition on the maximum amount of pre-generated information possible.
Additionally, this ordering guarantees that the self-driving car is always the
first to select an action at each timestep, in accordance with the guidelines
for the WOMD sim agents challenge (Montali et al., 2023).

To sample an arbitrarily long scenario, we have the option to sample up to
$t<T=32$ steps before computing new 24-agent subsets. Computing new subsets
every timestep ensures that the agents within a subset are always close to
each other, but has the computational downside of requiring the transformer
decoder key-value cache to be flushed at each timestep. For our submission, we
compute the subsets at timesteps $t\in\\{10,34,58\\}$.

While the performance of our model under the WOMD sim agents metrics was
largely unaffected by the choice of the hyperparameters above, we found that
the metrics were sensitive to the temperature and nucleus that we use when
sampling from the model. We use a temperature of 1.5 and a nucleus of 1.0 to
achieve the results in Tab. 1. Our intuition for why larger temperatures
resulted in larger values for the sim agents metric is that the log likelihood
penalizes lack of coverage much more strongly than lack of calibration, and
higher temperature greatly improves the coverage.

Finally, we observed that, although the performance of our model sampling with
temperature 1.5 was better than all prior work for interaction and map-based
metrics as reported in Tab. 3, the performance was worse than prior work along
kinematics metrics. To test if this discrepancy was a byproduct of
discretization, we trained a “heading smoother” by tokenizing trajectories,
then training a small autoregressive transformer to predict back the original
heading given the tokenized trajectory. On tokenized ground-truth
trajectories, the heading smoother improves heading error from 0.58 degrees to
0.33 degrees. Note that the autoregressive design of the smoother ensures that
it does not violate the closed-loop requirement for the Sim Agents Benchmark.
The addition of this smoother did improve along kinematics metrics slightly,
as reported in Tab. 3. We reserve a more rigorous study of how to best improve
the kinematic realism of trajectories sampled from discrete sequence models
for future work.

Table 3: WOMD sim agents validation

Method Realism Meta metric $\uparrow$ Kinematic metrics $\uparrow$ Interactive
metrics $\uparrow$ Map-based metrics $\uparrow$ $\tau=1.25$,
$p_{\mathrm{top}}=0.995$ 0.5176 0.3960 0.5520 0.6532 $\tau=1.5$,
$p_{\mathrm{top}}=1.0$ 0.5312 0.3963 0.5838 0.6607 $\tau=1.5$,
$p_{\mathrm{top}}=1.0$, w/ $h$-smooth 0.5352 0.4065 0.5841 0.6612

###  A.6 Additional Ablation Results

#### Full Control

In Fig. 16, we find the sampled scenario with minimum corner distance to the
ground-truth scenario and plot that distance as a function of the number of
timesteps that are provided at initialization. When the initialization is a
single timestep, the minADE of both models that take into account intra-
timestep dependence improves. As more timesteps are provided, the effect
diminishes, as expected. We visualize a small number of rollouts in the full
autonomy setting in Fig. 17, and videos of other rollouts can be found on our
project page.

#### Partial Control

To quantitatively evaluate these rollouts, we measure the collision rate and
visualize the results in Fig. A.7. Of course, we expect the collision rate to
be high in these scenarios since most of the agents in the scene are on
replay. For Trajeglish models, we find that when the autonomous agent is the
first in the permutation to choose an action, they reproduce the performance
of the model with no intra-timestep dependence. When the agent goes last
however, the collision rate drops significantly. Modeling intra-timestep
interaction is a promising way to enable more realistic simulation with some
agents on replay, which may have practical benefits given that the
computational burden of simulating agents with replay is minimal. In Fig. 18,
we visualize how the trajectory for agents controlled by Trajeglish shifts
between the full autonomy setting and the partial autonomy setting. The agent
follows traffic flow and cedes the right of way when replay agents ignore the
actions of the agent controlled by the traffic model.

Figure 16: Full Autonomy minADE As we seed the scene with a longer
initialization, the no-intra model and our model converge to similar values,
and all models improve. When initialized with only a single timestep, the
performance gap between models that take into account intra-timestep
interaction and models that do not is significant.

###  A.7 Additional Analysis

#### Data and Training Statistics

We report a comparison between the number of tokens in WOMD and the number of
tokens in datasets used to train GPT-1 and GPT-2 in Tab. 5. Of course, a text
token and a motion token do not have exactly the same information content, but
we still think the comparison is worth making as it suggests that WOMD
represents a dataset size similar to BookCorpus Zhu et al. (2015) which was
used to train GPT-1 and the scaling curves we compute for our model shown in
Fig. 4.2 support this comparison. We also report the number of tokens
collected per hour of driving to estimate how many hours of driving would be
necessary to reach a given token count. In Tab. 5, we document the extent to
which using mixed precision and flash attention improves memory use and speed.
Using these tools, our model takes 2 days to train on 4 A100s.

#### Context Length

Context length refers to the number of tokens that the model has to condition
on when predicting the distribution over the next token. Intuitively, as the
model is given more context, the model should get strictly better at
predicting the next token. We quantify this effect in Fig. A.7. We find that
the relative decrease in cross entropy from increasing the context length
drops off steeply for our model for pedestrians and cyclists, which aligns
with the standard intuition that these kinds of agents are more markov. In
comparison, we find a significant decrease in cross entropy with up to 2
seconds of context for vehicles, which is double the standard context length
used for vehicles on motion prediction benchmarks (Ettinger et al., 2021;
Caesar et al., 2019).

figurePartial control collision rate We plot the collision rate as a function
of rollout time when the traffic model controls only one agent while the rest
are on replay. We expect this collision rate to be higher than the log
collision rate since the replay agents do not react to the dynamic agents. We
note that the collision rate decreases significantly just by placing the agent
last in the order, showing that the model learns to condition on the actions
of other agents within a single timestep effectively.

figureContext Length We plot the negative log-likelihood (NLL) when we vary
the context length at test-time relative to the NLL at full context. Matching
with intuition, while pedestrians and cyclists are more markov on a short
horizon, interaction occurs on a longer timescale for vehicles.

Table 4: Dataset comparison by tokens

tokens rate (tok/hour) nuScenes 3M 0.85M WOMD 1.5B 1.2M WOMD (moving) 1.1B
0.88M BookCorpus (GPT-1) 1B - OpenWebText (GPT-2) 9B -

Table 5: Training efficiency

memory speed (steps/hour) no intra 14.7 MiB 8.9k trajeglish (mem-efficient)
7.2 MiB 11.1k trajeglish (bfloat16+flash) 5.6 MiB 23.0k

Figure 17: Full controll rollouts Additional visualizations of full control samples from our model. The model captures the collective behavior of agents at an intersection and maneuvers such as U-turns. |
---|---
|
Figure 18: Partial control comparison We visualize the effect of controlling
only one agent with Trajeglish and controlling the others with replay. The
left scene in each pair is a full control sample from Trajeglish. The right
scene is generated by placing all green cars on fixed replay tracks and
controlling the single blue car with Trajeglish. Our model reacts dynamically
to other agents in the scene at each timestep.


# Text Line Segmentation for Challenging Handwritten Document Images Using
Fully Convolutional Network

Berat Barakat, Ahmad Droby, Majeed Kassis and Jihad El-Sana  The Department of
Computer Science
Ben-Gurion University of the Negev
Email: {berat, drobya, majeek<EMAIL_ADDRESS>
###### Abstract

This paper presents a method for text line segmentation of challenging
historical manuscript images. These manuscript images contain narrow interline
spaces with touching components, interpenetrating vowel signs and inconsistent
font types and sizes. In addition, they contain curved, multi-skewed and
multi-directed side note lines within a complex page layout. Therefore,
bounding polygon labeling would be very difficult and time consuming. Instead
we rely on line masks that connect the components on the same text line. Then
these line masks are predicted using a Fully Convolutional Network (FCN). In
the literature, FCN has been successfully used for text line segmentation of
regular handwritten document images. The present paper shows that FCN is
useful with challenging manuscript images as well. Using a new evaluation
metric that is sensitive to over segmentation as well as under segmentation,
testing results on a publicly available challenging handwritten dataset are
comparable with the results of a previous work on the same dataset.

##  I Introduction

Historical handwritten documents are valuable since they connect past and
present. Commonly they are converted into digital form for being easily
available to scholars worldwide. However, digital historical documents pose
real challenges for automatic writer identification, keyword searching, and
indexing. Text line segmentation of document images is an essential pre-
processing operation for these automatizing problems. The problems for text
line segmentation of handwritten documents consist of touching, overlapping
and crowded characters and vowel signs among consecutive text lines besides
narrow interline spacing (Figure 1).

In addition to the problems of handwritten documents, challenging handwritten
documents contain various writing styles with inconsistent font types and font
sizes through multi-skewed, multi-directed and curved text lines (Figure 2).

Several text line extraction methods for handwritten documents have been
proposed. Projection method was initially used for printed documents [1, 2]
then modified for skewed [3, 4] and multi-skewed documents [5]. Smearing
method [6] which fills the space between consecutive foreground pixels can be
used on skewed documents [7] as well. Grouping method aggregates pixels or
connected components in a bottom up strategy and is superior in case of skewed
and curved text lines [8, 9]. Machine learning algorithms, a type of grouping
method, handle text line segmentation as a pixel classification problem. Pixel
classification can be done in a sliding window manner [10, 11] which is not
desirable due to redundant and expensive computation of overlapping areas in
the sliding windows. On the other hand, dense prediction does not suffer from
redundant computation and has been successfully used for text line
segmentation of handwritten documents [12, 13].

Figure 1: Text line segmentation problems with regular handwritten documents
Figure 2: Additional text line segmentation problems with challenging
handwritten documents. Various writing styles are also noticeable.

However, text line extraction of challenging documents has not been
extensively studied. This paper provides a dataset (https://www.cs.bgu.ac.il/
vml/) of challenging documents with multi-skewed, multi-directed and curved
handwritten text lines. It then describes text line segmentation of this
dataset using Fully Convolutional Network (FCN). We also propose a new
evaluation metric that is sensitive to both, over and under segmentation of
lines in contrast to the available metrics. Using the new evaluation metric we
show that FCN based method is comparable to Cohen et al.’s method [9].

In the rest of the paper we describe our method and the new evaluation metric
in detail, and present the challenging dataset and report experimental
results. After comparing results we conclude and discuss the future
directions.

##  II Method

Fully Convolutional Network has made great improvements in object segmentation
field [14]. It is an end to end semantic segmentation framework that extracts
the features and learns the classifier function simultaneously. FCN inputs the
original images and their pixel level annotations for learning the hypothesis
function that can predict whether a pixel belongs to a text line label or not.
So the crucial question is how to annotate the text lines. Baseline labeling
is not applicable to all the alphabets whereas bounding polygon is applicable
but very cumbersome for crowded documents [15]. Instead of baseline or
bounding polygon, we used line mask labeling that connects the characters in
the same line (Figure 4). A line mask disregards diacritics and touching
components between lines.

###  II-A FCN architecture

The FCN architecture (Figure 3) we used is based on the FCN proposed for
semantic segmentation [14]. First five blocks, encoder part, follow the design
of VGG 16-layer network [16] except the discarded final layer. The encoder
consists of five convolutional blocks. Each convolutional block contains a
number of convolutional layers followed by a max pooling layer. Through the
encoder, input image is downsampled, and the filters can see coarser
information with larger receptive field. Then the decoder part of FCN
upsamples coarse outputs to dense pixels. Upsampling is done by transpose
convolution by applying a convolution filter with a stride equal to
$\frac{1}{f}$, for upsampling by a factor $f$.

FCN has two types, FCN8 and FCN32, according to the upsampling factor used in
the last layer. FCN32 upsamples the last convolutional layer by $f=32$ at one
time. However, particularly FCN8 architecture was selected because it has been
successful in page layout analysis of a similar dataset [17]. FCN8 adds final
layer of encoder to the lower layers with finer information, then upsamples
the combined layer back to the input size. Default input size of VGG is
$224\times 224$, which does not cover more than 2 main text lines and 3 side
text lines. To include more context we changed the input size to $320\times
320$ pixels. We also changed the output channel to 2 which is the number of
classes, text line or background.

Figure 3: The FCN architecture. Pooling and prediction layers are shown as
grids that show relative coarseness. Convolutional layers are shown as
vertical lines. FCN8 4 times upsamples the final layer, 2 times upsamples the
pool4 layer and combine them with pool3 layer finally to upsample to input
size.

###  II-B Pre-processing

We binarize the 30 document images, each with an approximate size of
$3000\times 4000$, by applying an adaptive binarization method for historical
documents [18]. Binarized images were inverted before inputting them to the
FCN. Then we manually annotated the line masks on the document images. A
sequence of original, binarized and labeled document images is demonstrated in
Figure 4. Finally a total of $50.000$ and $6.000$ random patches of size
$320\times 320$ were generated for training and validation sets of each fold
respectively.

Figure 4: A sequence of original, binarized and labeled document images.
Random patches for training are generated from the binarized and labeled
images.

###  II-C Training and testing

We applied 6 fold cross validation scheme for the experiments. Each fold was
split into train, validation and test sets. In each fold, training continued
for 80 epochs and the model with the least validation loss value was saved.
The best model was then used to predict the corresponding test set. This
training procedure ensures generalizability of the proposed model. The FCN was
trained by a batch size of 16, using Stochastic Gradient Descent (SGD) with
momentum equals to $0.9$ and learning rate equals to $0.001$. VGG was
initialized with its publicly available pre-trained weights.

During the testing, a sliding window of size $320\times 320$ was used for
prediction, but only the inner window of size $100\times 100$ was considered.
Page was padded with black pixels at its right and bottom sides if its size is
not an integer multiple of the sliding window size, in addition to padding it
at 4 sides for considering only the central part of the sliding window.

###  II-D Post-processing

Occasionally predicted line masks were disconnected. Thus, we needed to post-
process the FCN output. Given a predicted line mask image, firstly the
orientation of each connected component was computed. Then the image was split
into $N$ layers where each layer contains the connected components with same
orientation. Later a directional morphological operation was applied on each
layer. Resulting layers at the end were combined back using a pixel-wise OR
operation.

Let $C=\\{c_{1},c_{2},...,c_{M}\\}$ is the set of connected components in the
predicted line mask image. $C$ is further divided into $N$ intersecting
subsets $B_{1},B_{2},...,B_{N}\subseteq C$ such that:

$B_{i}=\\{c_{i}:\alpha(c_{i})^{2}|v_{j}^{T}\cdot\theta(c_{i})|<\epsilon\\}$
(1) $i=1,2,\dots M,j=1,2,\dots N$

$v_{j}=(\cos(j\frac{\pi}{N}),\sin(j\frac{\pi}{N}))$ (2)
$\alpha(c)=\frac{R_{maj}}{R_{maj}+R_{min}}$ (3)

where $v_{j}\in[0,\pi]$ is a particular orientation and $\epsilon\in[0,1]$ is
the threshold for selecting the connected components perpendicular to this
particular orientation. $R_{maj}$ and $R_{min}$ are the major and minor axes
of the fitted ellipse to the connected component $c$ respectively.
$\alpha(c)\in[0.5,1]$ indicates how sure are we about the orientation of the
component $c$. $\theta(c)$ is the unit vector that represents the orientation
of the fitted ellipse to the connected component $c$. Ellipse fitting was done
using the algorithm described in [19].

Eventually for each subset $B_{i}$ a morphological operation with a narrow
kernel in the orientation of this subset was applied. Figure 5 shows the
result of post-processing on a sample predicted line mask image.

Figure 5: Post processing phases: (a) Predicted line mask may have
disconnected components. (b) For each component an ellipse (red) is fitted and
its orientation vector $\theta(c)$ (blue) is computed. (c) Morphological
dilation is applied to each component with a narrow kernel in the direction of
its fitted ellipse.

###  II-E Connectivity Component Based Line Extraction Accuracy Metric

Available evaluation methods for text line segmentation either use a pixel-
wise matching mostly normalized by line length or maximum overlap according to
a certain threshold between the extracted and annotated lines. These methods
have their short-comings. Thus, we present a different evaluation method that
provides a better picture of the results.

The theoretical basis is as follows. A line extraction algorithm succeeds in
extracting a complete text line if it has succeeded in finding all the
connected components of this line. That is if the algorithm labels all the
connected components of a line with the same label, then it has successfully
extracted this line without any errors. This is in contrast to having multiple
labels, over segmentation, or extracting part of the connected components,
under segmentation, along the same text line.

To describe the new metric, we define the term connectivity component. A
connectivity component is the connection between two consecutive components
with the same label. The number of connectivity components in a line is equal
to the number of connectivity components between every two consequent
connected components and in addition to it a beginning of line connectivity
component. The extra connectivity component handles cases where a line
contains one connected component only. _C_ omplete extraction of a line with
several connectivity components is extracting all its connectivity components
and assigning them the same label.

To quantify the new metric we define recall and precision for calculating
F-measure. Recall is the number of connectivity components extracted by the
algorithm in a line, out of all connectivity components found in the
corresponding line in ground truth. Precision is the number of correct
connectivity components extracted by the algorithm in a line out of all
connectivity components extracted by the algorithm. Note that some
connectivity components extracted by the algorithm are not found in the ground
truth, and some connectivity components are found in the ground truth but not
extracted by the algorithm. First type of error is quantified in the precision
part of the metric, while the latter type of error is quantified in the recall
part of the metric.

Let $G=\\{g_{1},g_{2},g_{3},\dots g_{m}\\}$ is the set of connected components
of a line in the ground truth, $E_{i}\in\\{E_{1},E_{2},E_{3},\dots E_{n}\\}$
is the set of extracted lines such that $E_{i}\cap G\neq\emptyset$, then for
this line in the ground truth, recall ($R$) and precision ($P$) is:

$R=\sum\limits_{i}{\frac{|E_{i}\cap G|-1}{|G|-1}}$ (4)
$P=\frac{\sum\limits_{i}{|E_{i}\cap G|-1}}{\sum\limits_{i}{|E_{i}|-1}}$ (5)

The recall definition penalizes over segmentation of a line where an
extraction algorithm assigns multiple labels to the components of a single
line. In contrast, the precision definition penalizes under segmentation where
an extraction algorithm incorrectly assigns a line label to the components
that are not in the ground truth of this line (Figure 6).

Figure 6: Connectivity component based metric penalizes under segmentation by
its precision definition and over segmentation by its recall definition.

##  III Dataset

Although several benchmark datasets [20, 21, 22] of handwritten document
images are available, a challenging document dataset is absent. We collected a
set of challenging document images from the Islamic Heritage Project (IHP),
Harvard. This dataset is publicly available (https://www.cs.bgu.ac.il/ vml/).

The challenging dataset contains 30 pages from two different manuscripts. It
is written in Arabic language and contains 2732 text lines where a
considerable amount of them are multi-directed, multi-skewed or curved. Ground
truth where text lines were labeled manually by line masks is also available
in the dataset.

##  IV Results

We tested the proposed system on the new challenging handwritten document
dataset. In each fold we trained FCN on 50.000 patches randomly cropped from
20 pages, validated on 6.000 patches randomly cropped from 5 pages and tested
on 5 whole pages using a sliding window. Predicted line mask images were then
post-processed with $N=10$ and $\epsilon=0.2$. Extracted text lines were
evaluated using the new metric to calculate the F-measure.

Entire training took around 9 days. Visualization of the first convolutional
layer filters shows that network have learned and filters have converged
(Figure 7). The model achieved $89\%$ training accuracy and $88\%$ validation
accuracy on average. Two characteristics of the dataset lead the model lacking
to overfit to the training set. First it contains two manuscripts with 6 and
24 pages. The manuscript with 6 pages caused most of the errors. Second,
although dataset contains considerable amount of multi-skewed, multi-directed
and curved lines, they spatially cover smaller area due to smaller font size.
This lead to less number of random patches with skewed or curved lines in
relative to the number of random patches with regular lines.

Figure 7: Visualization of the filters in the first convolutional layer.

Table I shows the performance of our method compared with the method of Cohen
et al.[9]. Their approach achieved outstanding results on ICDAR2009 [20] and
ICDAR2013 [21] datasets. We run their publicly available code
(http://www.cs.bgu.ac.il/ rafico/LineExtraction.zip) on the challenging
handwritten dataset.

TABLE I: Comparison with the method of Cohen et al. Method | Recall | Precision | F-measure
---|---|---|---
Proposed | 0.82 | 0.78 | 0.80
Cohen et al.[9] | 0.74 | 0.60 | 0.66
Figure 8: Sample image of ground truth and corresponding outputs of Cohen et
al. [9] and FCN. Lower precision values show that both method tend to under
segment. Most errors of FCN method occur at curved areas whereas most errors
of method of Cohen et al. occur at the main text areas.

Our method outperforms the method of Cohen et al. in terms of both recall and
precision. Both methods have lower precision values than recall values. This
demonstrates that most of their errors are due to wrongly connected lines in
their output. Therefore both method tend to under segment more than over
segment. We have noticed that in the output of our method, wrongly connected
lines mostly crop up at the curved areas in contrast to the output of Cohen et
al where the wrongly connected lines are mostly crop up at the main text
areas. The former was a result of small number of training patches with curved
lines. Curved lines can be long but their curved part covers relatively a
small spatial area which is one or two corner parts of a page. The latter was
a result of small number of main text lines in relative to the number of side
text lines in a page, where the average height of text lines converges to the
height of side text lines. Therefore method of Cohen et al., which runs
according to the average height of text lines, has most errors in main text
areas. Figure 8 shows some qualitative results for the latter and the former
types of errors on the challenging dataset.

##  V Conclusion

This paper introduces challenging handwritten documents, presents a dataset of
challenging handwritten documents and its text line segmentation using FCN.
Line mask labeling is less cumbersome for challenging handwritten documents
and is a proper way for FCN training. We have also defined a new evaluation
metric with the concept of connectivity component. This metric is sensitive to
both over and under segmentation. New metric is used to validate the proposed
method on the challenging handwritten dataset. As a future work, performance
on curved text lines can be improved by augmenting patches with curved lines.

## Acknowledgment

The authors would like to thank the support of the Frankel Center for Computer
Science at Ben-Gurion University of the Negev.

## References

  * [1] J. Ha, R. M. Haralick, and I. T. Phillips, “Document page decomposition by the bounding-box project,” in _Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on_ , vol. 2. IEEE, 1995, pp. 1119–1122.
  * [2] R. Manmatha and N. Srimal, “Scale space technique for word segmentation in handwritten documents,” _Lecture notes in computer science_ , pp. 22–33, 1999.
  * [3] M. Arivazhagan, H. Srinivasan, and S. Srihari, “A statistical approach to handwritten line segmentation,” _Document Recognition and Retrieval XIV, Proceedings of SPIE, San Jose, CA_ , pp. 6500T–1, 2007.
  * [4] I. Bar-Yosef, N. Hagbi, K. Kedem, and I. Dinstein, “Line segmentation for degraded handwritten historical documents,” in _Document Analysis and Recognition, 2009. ICDAR’09. 10th International Conference on_. IEEE, 2009, pp. 1161–1165.
  * [5] N. Ouwayed and A. Belaïd, “A general approach for multi-oriented text line extraction of handwritten documents,” _International Journal on Document Analysis and Recognition_ , pp. 1–18, 2012.
  * [6] K. Y. Wong, R. G. Casey, and F. M. Wahl, “Document analysis system,” _IBM journal of research and development_ , vol. 26, no. 6, pp. 647–656, 1982\.
  * [7] A. Alaei, U. Pal, and P. Nagabhushan, “A new scheme for unconstrained handwritten text-line segmentation,” _Pattern Recognition_ , vol. 44, no. 4, pp. 917–928, 2011.
  * [8] S. S. Bukhari, F. Shafait, and T. M. Breuel, “Script-independent handwritten textlines segmentation using active contours,” in _Document Analysis and Recognition, 2009. ICDAR’09. 10th International Conference on_. IEEE, 2009, pp. 446–450.
  * [9] R. Cohen, I. Dinstein, J. El-Sana, and K. Kedem, “Using scale-space anisotropic smoothing for text line extraction in historical documents,” in _International Conference Image Analysis and Recognition_. Springer, 2014, pp. 349–358.
  * [10] B. Moysset, C. Kermorvant, C. Wolf, and J. Louradour, “Paragraph text segmentation into lines with recurrent neural networks,” in _Document Analysis and Recognition (ICDAR), 2015 13th International Conference on_. IEEE, 2015, pp. 456–460.
  * [11] J. Pastor-Pellicer, M. Z. Afzal, M. Liwicki, and M. J. Castro-Bleda, “Complete system for text line extraction using convolutional neural networks and watershed transform,” in _Document Analysis Systems (DAS), 2016 12th IAPR Workshop on_. IEEE, 2016, pp. 30–35.
  * [12] Q. N. Vo and G. Lee, “Dense prediction for text line segmentation in handwritten document images,” in _Image Processing (ICIP), 2016 IEEE International Conference on_. IEEE, 2016, pp. 3264–3268.
  * [13] G. Renton, C. Chatelain, S. Adam, C. Kermorvant, and T. Paquet, “Handwritten text line segmentation using fully convolutional network,” in _Document Analysis and Recognition (ICDAR), 2017 14th IAPR International Conference on_ , vol. 5. IEEE, 2017, pp. 5–9.
  * [14] J. Long, E. Shelhamer, and T. Darrell, “Fully convolutional networks for semantic segmentation,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 3431–3440.
  * [15] T. Grüning, R. Labahn, M. Diem, F. Kleber, and S. Fiel, “Read-bad: A new dataset and evaluation scheme for baseline detection in archival documents,” _arXiv preprint arXiv:1705.03311_ , 2017.
  * [16] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” _arXiv preprint arXiv:1409.1556_ , 2014.
  * [17] B. Barakat and J. El-Sana, “Binarization free layout analysis for arabic historical documents using fully convolutional networks,” in _Arabic Script Analysis and Recognition (ASAR), 2nd International Workshop_. IEEE, 2018, pp. 26–30.
  * [18] I. Bar-Yosef, I. Beckman, K. Kedem, and I. Dinstein, “Binarization, character extraction, and writer identification of historical hebrew calligraphy documents,” _International Journal of Document Analysis and Recognition (IJDAR)_ , vol. 9, no. 2-4, pp. 89–99, 2007.
  * [19] A. W. Fitzgibbon, R. B. Fisher _et al._ , “A buyer’s guide to conic fitting,” _DAI Research paper_ , 1996.
  * [20] B. Gatos, N. Stamatopoulos, and G. Louloudis, “Icdar2009 handwriting segmentation contest,” _International Journal on Document Analysis and Recognition (IJDAR)_ , vol. 14, no. 1, pp. 25–33, 2011.
  * [21] N. Stamatopoulos, B. Gatos, G. Louloudis, U. Pal, and A. Alaei, “Icdar 2013 handwriting segmentation contest,” in _Document Analysis and Recognition (ICDAR), 2013 12th International Conference on_. IEEE, 2013, pp. 1402–1406.
  * [22] M. Diem, F. Kleber, S. Fiel, T. Grüning, and B. Gatos, “cbad: Icdar2017 competition on baseline detection,” in _Document Analysis and Recognition (ICDAR), 2017 14th IAPR International Conference on_ , vol. 1. IEEE, 2017, pp. 1355–1360.