# QButterfly: Lightweight Survey Extension for Online User Interaction Studies
for Non-Tech-Savvy Researchers

Nico Ebert<EMAIL_ADDRESS>0000-0002-9683-4792 Zurich University of
Applied Sciences, School of Management and LawTheaterstrasse
17WinterthurZurichSwitzerland8401 ,  Björn Scheppler  Zurich University of
Applied Sciences, School of Management and LawTheaterstrasse
17WinterthurZurichSwitzerland8401 ,  Kurt Ackermann  Zurich University of
Applied Sciences, School of Management and LawTheaterstrasse
17WinterthurZurichSwitzerland8401 and  Tim Geppert  Zurich University of
Applied Sciences, School of Management and LawTheaterstrasse
17WinterthurZurichSwitzerland8401

(2023)

###### Abstract.

We provide a user-friendly, flexible, and lightweight open-source HCI toolkit
(github.com/QButterfly) that allows non-tech-savvy researchers to conduct
online user interaction studies using the widespread Qualtrics and LimeSurvey
platforms. These platforms already provide rich functionality (e.g., for
experiments or usability tests) and therefore lend themselves to an extension
to display stimulus web pages and record clickstreams. The toolkit consists of
a survey template with embedded JavaScript, a JavaScript library embedded in
the HTML web pages, and scripts to analyze the collected data. No special
programming skills are required to set up a study or match survey data and
user interaction data after data collection. We empirically validated the
software in a laboratory and a field study. We conclude that this extension,
even in its preliminary version, has the potential to make online user
interaction studies (e.g., with crowdsourced participants) accessible to a
broader range of researchers.

online user interaction studies, online experiments, Qualtrics, LimeSurvey,
open source, HCI toolkit

††copyright: acmcopyright††journalyear: 2023††doi:
10.1145/3544548.3580780††conference: 2023 CHI Conference on Human Factors in
Computing Systems; April 23-28, 2023; Hamburg††price: 15.00††isbn:
978-1-4503-XXXX-X/18/06††ccs: Human-centered computing Laboratory
experiments††ccs: Human-centered computing Field studies††ccs: Human-centered
computing User studies††ccs: Human-centered computing Systems and tools for
interaction design

##  1\. Introduction

Companies such as Alphabet, Amazon, and Microsoft, permanently expose their
users to user interaction studies in the form of simultaneous experiments to
optimize their websites’ effectiveness (Kohavi and Longbotham, 2007; Tang et
al., 2010). For example, Microsoft’s Bing search engine team studied the
effect of additional site links in their search engine ads (Figure 1) and, as
a result, was able to increase revenue by “tens of millions of dollars per
year with neutral user impact” (Kohavi and Longbotham, 2017). These
experiments are often carried out directly in the field with a specific
percentage of (often unknowing) users involved over some time (Kohavi and
Longbotham, 2007), and in-situ, as participants use their everyday devices
instead of laboratory equipment. This makes it possible to observe user
behavior in a real-world environment instead of an artificial one (Baravalle
and Lanfranchi, 2003). Platforms like Optimizely allow website owners to
conduct online user interaction experiments on their websites in real-time
(Optimizely, 2021), and online user interaction studies do not necessarily
have to be carried out in the form of experiments (e.g., randomization,
different stimuli). Website owners can also ask users for qualitative feedback
and integrate analytics tools, such as Matomo, Open Web Analytics, or Google
Analytics, to observe user behavior and optimize their website accordingly
(e.g., (Hasan et al., 2009)).

The figure shows two different bing ads, one in a control condition and a
slightly different one in a treatment condition

Figure 1. Bing ads without (top) and with site links (bottom) as example
stimuli in an online user interaction study (Kohavi and Longbotham, 2017)

However, unlike in these mostly correlational studies conducted by
practitioners, researchers in HCI and related disciplines typically want to
develop and test a theory or design theory-guided artifacts. Therefore, they
need a higher level of control than the abovementioned examples and different
instruments to conduct studies (e.g., for screening, controlling for
extraneous variables, or carrying out attention and manipulation checks).
There is a rising demand among HCI researchers to conduct controlled studies
at scale (Egelman et al., 2014; Findlater et al., 2017). Therefore,
participants are often recruited from a panel or platform, such as Amazon
Mechanical Turk (MTurk), and directed to other platforms that help to conduct
surveys, experiments, or usability tests (e.g., (Kittur et al., 2008)).

Despite the popularity of controlled online user interaction studies,
researchers have many technical challenges to overcome (Hirth et al., 2017).
First, it remains laborious for scientists to conduct controlled online user
interaction studies, especially with a large number of participants (e.g.,
collecting data from multiple tools that present either survey or stimulus
elements) (Hirth et al., 2017). Second, researchers who wish to develop such
studies need to have software development skills and be able to develop the
required functions in a customized manner (e.g., to identify participants
during the study) (Hirth et al., 2017). Lastly, researchers and study
participants need to use multiple and often isolated tools and websites (e.g.,
survey website, stimulus website), which is especially error-prone in a
complex study design with many users (Hirth et al., 2017). We are not aware of
any easy-to-use and open-source software suitable for settings that (i) allow
the use of standard experimental features, such as randomization, presentation
of multiple stimuli, and flexible questions and, at the same time, (ii)
ensures a consistent stimulus presentation even when users complete the study
using their own private equipment.

To address this need, this paper introduces the open-source QButterfly HCI
toolkit, which allows non-tech-savvy users to design controlled user
interaction studies using the widely available Qualtrics and LimeSurvey
platforms. QButterly has already successfully been used in HCI research (e.g.,
(Ebert et al., 2021, 2022)). Our software enhances existing survey platforms
with stimulus presentation and user-tracking features and consists of (i) a
premade survey template containing embedded JavaScript to manage the website
presentation and collect user-tracking data, (ii) a small JavaScript library
to be embedded into the website that tracks the user data and reports them to
the survey platform, and (iii) Excel scripts based on generic regular
expressions to analyze the collected data. We present two validation studies
demonstrating consistent data collection in a laboratory and a realistic,
crowdsourced setting.

##  2\. Related Work

The provision of toolkits that expand the existing repertoire of researchers
falls into the categories of “constructive research” (Oulasvirta and Hornbæk,
2016) and “code as a contribution” (Fogarty, 2017). There are several examples
where such toolkits have contributed significantly to scientific research in
the HCI domain and beyond (e.g., AWARE (Ferreira et al., 2015), psiTurk
(Gureckis et al., 2016), oTree (Chen et al., 2016)). To benefit other
researchers, toolkits must be evaluated with adequate measures (e.g.,
demonstration, usage, or a technical benchmark) (Ledo et al., 2018).

Researchers who want to conduct controlled user interaction studies typically
employ surveys, experiments, or usability tests (Lazar et al., 2017) and need
a collection of tools to present a stimulus (e.g., multiple websites), collect
data from users (e.g., via an online questionnaire) and observe user behavior
(e.g., via electronic notes). Stimuli can range from purely visual design
ideas with no user interaction to clickable website prototypes with limited
user interaction or fully developed websites with multiple interlinked web
pages. In the context of websites, to capture user interaction, the user must
be monitored along a “visitor path” across multiple linked web pages (Jansen,
2009; Hirth et al., 2017). A relatively simple tracking technique involves
capturing mouse clicks on specific areas of the stimulus (e.g., links clicked
on a website) or dwell time (e.g., time spent on a website before visiting
another one) (Jansen, 2009). More sophisticated tracking techniques may
involve recording mouse trajectories, keyboard inputs, or eye movements (e.g.,
to generate visual heat maps) (Acar et al., 2020; Nielsen and Pernice, 2009).

Whereas in traditional controlled user interaction studies in the lab (e.g.,
with students using lab computers), researchers have a high level of control
and can interact with the participants, controlled online user interaction
studies with crowdsourced subjects using their own personal devices pose
different challenges (Findlater et al., 2017). Especially in studies with many
anonymous participants, researchers have limited abilities to assist
participants (e.g., to prevent input mistakes). Researchers could easily
handle procedures in the lab, such as assigning a user to an experimental
condition, conducting an ex-ante survey (e.g., screening), asking a user to
visit several condition-specific websites, and conducting an ex-post survey
(e.g., usability experience). However, in online settings, this would not only
be prone to error (e.g., users accidentally switching between survey and
stimulus windows on their device) but require software development (e.g.,
keeping track of a specific user’s actions). To create studies with a better
user experience and a lower error susceptibility at a large scale, researchers
would have to overcome the technical disintegration of the required tools
(Hirth et al., 2017). They would have to develop software that neatly
integrates surveying, stimulus presentation, and behavior monitoring - at the
price of reinventing functionalities provided out of the box by existing web
analytics and survey tools.

Such requirements for controlled online user interaction studies also apply to
other types of online studies. For example, some cognitive-psychological
experiments, such as the Stroop test (Stroop, 1935), require the precise
measurement of stimulus presentation and reaction times. Many tools exist that
support researchers in conducting these kinds of studies online and provide
required timing precision (Bridges et al., 2020). Some require programming
skills, while others are even able to be used by non-tech-savvy researchers
(e.g., QRTEngine (Barnhoorn et al., 2015), Gorilla (Anwyl-Irvine et al.,
2020)). However, the focus of their stimulus presentation is not on a
realistic “look and feel” of a website (e.g., on a mobile device) as in user
interaction studies, nor on a comprehensive assessment of user behavior.
Therefore, these tools can neither present the required stimuli nor record the
user interaction with them.

To conduct controlled online user interaction studies, one could also consider
versatile software frameworks for online studies such as psiTurk (Gureckis et
al., 2016) or oTree (Chen et al., 2016); however, researchers would need to
have skills to develop the user interaction study in a programming language
such as Python. For HCI researchers that have previously only used survey
tools (e.g., Qualtrics) and have little to no programming skills or do not
have the ressources to invest time and effort into software development, there
is a hurdle to using these tools.

##  3\. Introducing QButterfly

QButterfly provides a lightweight approach for controlled online user
interaction studies that requires no special programming skills; it is
published under the MIT license. Its preliminary version allows embedding HTML
pages in Qualtrics and LimeSurvey, recording user clicks on the HTML elements,
and directly storing them on the survey platforms. Thanks to the integration,
a) existing features of the survey platforms can be used (e.g., question
types, random assignment to conditions), and participants do not have to
switch between different windows, b) it is not necessary to manually match
survey data and click data after the study (e.g., via IP address as in
(Goldstein, 2019)) and c) user click stream data can be analyzed in real-time
during the survey (e.g., to influence the survey flow based on user clicks).
For example, user ID matching would be required if a survey platform is
combined with a web analytics suite, such as Matomo, to analyze clickstreams
on the stimulus website. While such a combination may seem more powerful
because advanced analytics features would be available in such cases, it is
problematic because matching user IDs across platforms requires technical
skills or is associated with a disadvantage for study participants (e.g., they
need to enter an identifier on the stimulus website that needs to be stored).
Using web analytics results to influence an individual survey flow in real-
time during a survey would be even more complex to achieve for non-technical
users.

Figure 2 shows the system architecture of QButterfly, while users can be
recruited from any participant pool (e.g., Prolific, MTurk). The QButterfly
template hosted in a Qualtrics or LimeSurvey environment is used to set up
online user studies (e.g., collect qualitative feedback or conduct
experiments). Features, such as the random assignment of participants to
different conditions and the design of questions, take advantage of the easy-
to-use survey platform interface. The QButterfly survey template contains HTML
and JavaScript code that allows the user to display the stimulus webpage(s)
seamlessly in the survey. This can be as straightforward as one or multiple
static HTML web pages without server backend functionality. Furthermore, each
webpage is enriched with the QButterfly JavaScript library, which records the
user clicks and transfers them to the survey server. That means access to the
website is required, and user-interaction cannot be recorded on any Internet
website.

Figure 2. QButterfly architecture

The figure shows from left to right: a participant pool, the survey server,
and the web server hosting the stimulus website. QButterfly uses the
QButterfly template and controls the study flow via the survey. It displays
the website within the survey.

Figure 3 illustrates an exemplary study flow with a simple between-subjects
design in Qualtrics using QButterfly. At the study’s beginning, users consent
to participate and are screened. Next, they are randomly assigned to an
experimental condition that contains a particular survey question element.
This unique question has three purposes: (i) to display the website, (ii) to
“listen” to user events related to the website, and (iii) to record user
events on the survey platform.

First, the question element can present a different website in each condition.
Technically, it contains the HTML code of an inline frame (iframe), a broadly-
supported HTML element ((W3C, 2022)). An iframe is used to visually embed one
browser window (“child”) within another browser window (“parent”). In the case
of QButterfly, the stimulus website is embedded as a child window within the
survey’s parent window. During interaction with the website, the surrounding
Qualtrics elements (e.g., the button to go backward or forward) can be
disabled to avoid an unwanted interruption in the website presentation. The
termination of a specific user interaction episode can either be triggered by
a user event (i.e., a click on a particular element), or a pre-defined timer
that automatically activates survey elements or leads the participant to
subsequent survey questions (e.g., manipulation checks, demographics). Second,
the survey question element contains JavaScript code that “listens” to events
in the child window. These events are generated by the QButterfly JavaScript
embedded in the stimulus website. The current version of the JavaScript code
can record clicks on HTML elements, such as a hyperlink, together with a
timestamp.

Third, the questions record the user events in an “embedded field,” which can
be accessed during the survey from within the survey environment. For example,
data stored in the embedded field can be used to change the original survey
flow or other questions. Also, the embedded data is stored in the regular
survey dataset as additional variables and is thus readily accessible for data
analysis.

Figure 3. Illustrative survey flow on the survey platform with QButterfly

A survey is started, participants are assigned to a condition, the condition-
specific website is shown, tracking data is collected, and the survey is
continued e.g., with manipulation checks

##  4\. Creating and Analyzing a user interaction Study

Our open-source software provides a user-friendly data collection and analysis
pipeline for creating controlled online user interaction studies. A
demonstration and all survey and code files are available online, including
detailed instructions on setting up the software (github.com/QButterfly).
First, researchers import the “Qualtrics template” or “LimeSurvey template”,
which implements a simple user study including a stimulus website. They can
conduct the research and observe the recorded data through the survey
platform. The template also records a user’s browser properties (e.g., type,
version, screen resolution) by default, which are necessary parameters for
pre-studies before entering the field. For example, it might be required to
check the properties of a user’s device (e.g., screen dimensions) for screen-
out purposes or to adapt the stimulus website accordingly. The following
section describes the procedure for using QButterfly based on the “Qualtrics
template”. The procedure for LimeSurvey is very similar and described in the
GitHub repository.

First, the embedded fields shown in Table 1 must be configured on the survey
platform. The only exception is the “eventStream” field, which collects click
stream data. Most importantly, the address of the stimulus website(s) needs to
be defined. Afterward, the QButterfly JavaScript must be embedded into each
webpage of the website on which user behavior is tracked.

Table 1. Embedded fields on the survey platform Field |  Description
---|---
windowURL |  Address of stimulus website (e.g., https://www.mywebsite.com/index.HTML)
windowBorder |  Border size of stimulus website within survey window in pixels (e.g., “0” = no visible border)
windowHeight |  Height size of stimulus website within survey window in pixels (e.g., “640”)
windowWidth |  Width of stimulus website within survey window in pixels (e.g., “480”)
windowScroll |  Visible scrollbars of stimulus website within survey window (“yes” or “no”)
eventStream |  Chronological stream of tracking events of a user in the format “timestamp in ms since 01.01.1970 00:00:00 UTC#Event_ID” (e.g., 1630841029899#ready_demo.html; 1630841029900#load_demo.html; 1630841031050#MyLink;)
Note: The standard fields browser type, browser version, operating system,
screen resolution, java support, and user agent will also be collected by
QButterfly
Table 2. Excel functions for the analysis of the event stream Function |  Description
---|---
countEvent(Cell, Event_ID) |  Return the number of occurrences of a specific user event (e.g., MyLink) in an event stream.
countEventPattern(Cell, Event_ID_1, …) |  Returns the number of occurrences of a specific sequence of user events (e.g., MyLink1, MyLink2) in an event stream.
timestamp(Cell, Event_ID, occurrence) |  Returns the timestamp (ms since 01.01.1970 00:00:00 UTC) of the n-th occurrence of a specific event in an event stream.

Figure 4 shows how the QButterfly JavaScript is embedded in the code of a
simple webpage. To begin with, the required library JQuery is embedded
(“jquery.min.js”). Next, “qbutterfly.js” is embedded as this contains the
address of the survey server as a parameter (e.g.,
https://abcd.qualtrics.com). This allows the stimulus websites to send events
to the survey server. Finally, the HTML element to be tracked (e.g., an image,
link, checkbox) is marked with an ID tag with a unique name (e.g., MyLink).
This is a simple hyperlink in Figure 4. This ID later identifies the specific
user action within the events recorded in the “eventStream” field.

Figure 4. Code of an illustrative HTML page with a tracking script. The script
is embedded in the header (1) and contains the URL of the survey server (2).
The page contains an example link to be tracked, which is identified via the
ID ”MyLink” (3).

An html snippet is shown that shows how the QButterfly script is embedded. It
can be found on the GitHub site.

Events of a webpage are recorded in the “eventStream” field. Each recorded
event consists of a timestamp (ms since 01.01.1970 00:00:00 UTC) and an event
ID (e.g., 1629802674592#MyLink). Events are separated by the character “;”. An
event with the webpage name is generated when the first elements of a webpage
begin to load, and the user starts to see the webpage
(…#ready_demo.html)111QButterfly relies on the JQuery library to record all
events. The first QButterfly event is triggered when the page’s Document
Object Model (DOM) is ready to manipulate. This JQuery event is comparable to
the DOMContentLoaded provided by most browsers. The second event is generated
when all page resources, including all images, are loaded. This event listens
to “window.onload” (for details, see https://api.jquery.com/ready/).. A second
event is generated after all static page elements (e.g., images, CSS, scripts)
have been successfully loaded (…#load_demo.html). Additionally, each click on
an element – whether previously defined with an ID or not – will generate an
event (e.g., 1629802676308#MyLink, 1629802677000#Undefined).

To assure that the user can only see the webpage when it is fully loaded and
cannot interact with it beforehand, the code in Figure 5 can optionally be
added. QButterfly will make the page visible only after all static elements
are loaded.

Figure 5. Code to hide HTML page until all static elements are loaded

An html snippet is shown that shows how the website is disabled and first
shown. It can be found on the GitHub site.

To analyze the recorded event data of a particular user or between users, the
survey results can be exported from the survey platform (e.g., csv, xlsx).
QButterfly provides an Excel template (“qbutterfly.xlsx”). This contains a set
of “visual basic for application” (VBA) macros for data analysis. The
implemented functions “countEvent”, “countEventPattern”, and “timestamp” shown
in Table 2 allow us to identify specific events or event patterns and
calculate intervals between events. The functions are based on regular
expressions and can be combined with higher-level functions. For example,
given recorded event data in the Excel cell A1, the function
“=abs(timestamp(A1, “MyLink2”, 1) - timestamp(A1, “MyLink1”, 1))” would return
the interval (in ms) between the user’s first click on MyLink1 and the first
click on MyLink2.

##  5\. Special Considerations for Online Use

As described in the section “Introducing QButterfly,” the overall architecture
is based on the survey platform and the stimulus website. Therefore, the
survey server and the website hosting must be available during the study. For
this reason, in situations with many (concurrent) users accessing the stimulus
website, availability must be guaranteed by an appropriate configuration. If
necessary, performance testing must be carried out in advance.

Allowing participants to complete studies on their own devices, rather than in
a controlled lab setting, poses several challenges for collecting reliable and
precise tracking information (e.g., (Mathur and Reichling, 2019)). For
example, a user’s browser in the field could theoretically render the stimulus
material differently than the researcher expects because the user has a
magnification function enabled or the screen resolution is too small to
display the complete website. Different user devices with various performances
could also lead to different timing information. Like the survey platform,
QButterfly requires JavaScript to be enabled in the browser. However, users
can disable JavaScript in their browsers or block specific JavaScript codes,
such as cross-site JavaScript or iframes used by QButterfly. In the context of
online user studies, the most efficient way to mitigate these potential
problems is to conduct pre-studies to assess the target population (e.g.,
typical screen dimensions, active blocker extensions, and visual impairments).

##  6\. Validation of the Software

We validated the software in two studies – a laboratory study and a field
study with crowdsourced subjects. The focus of the laboratory study was to
evaluate whether the tracking information was valid and reliable. The field
study investigated whether data collection is reliable in a natural
environment with a broad range of devices, browsers, and individual settings.
Before the two studies, the general compatibility of QButterfly with different
devices and browser combinations was tested. These were Windows 10 (Chrome,
Edge, Firefox, Internet Explorer), macOS (Chrome, Safari), Android (Chrome),
and iOS (Chrome, Safari). Except for Internet Explorer, it worked on all
platforms (see “Limitations”).

###  6.1. Laboratory Study

####  6.1.1. Design

The goal of the laboratory study was to evaluate whether a series of actions
generated by a user is tracked correctly in terms of the type and sequence of
the recorded events and their timestamps. Regarding the time information, an
“adequate” accuracy is sufficient as compared to to high and precise temporal
resolution that would be required in psychophysics experiments, for instance
(e.g., (Anwyl-Irvine et al., 2021)). As an indication, web analytics tools,
such as Google Analytics, typically report timing information in seconds
instead of milliseconds (Google, 2021). An additional concern is that the time
a webpage takes to load is influenced by many factors, such as the hosting
service, the network connection to and from the server, the complexity of the
website (e.g., size, images, third-party content), and the performance of the
client and the browser itself222Concerning images, these problems can be
addressed by pre-loading the images before display (Garaizar and Reips, 2019).
These factors can lead to page load time variances in the range of seconds
(e.g., (Kelton et al., 2020)). A website’s content can also be dynamically
loaded even after it has been successfully loaded for the first time.
Therefore, the interpretation of timing information is highly dependent on the
specific context.

We designed a simple study for the laboratory setting based on the “QButterfly
template” for Qualtrics that recorded the user interaction. We chose a more
straightforward approach instead of using external devices to register stimuli
and trigger events (e.g., a BBTK photodiode and robotic actuator (Bridges et
al., 2020)) since we considered the timing precision sufficient for our
purposes. We hosted a realistic stimulus with multiple linked webpages based
on HTML, CSS, and JavaScript (a fitness tracking website) on Amazon Web
Services and simulated user interaction directly on the computer that showed
the stimulus. Two configurations based on the most popular browsers, Chrome
(95.0, Windows 10, Dell Latitude 1.9GHz i7, 16GB Ram) and Safari (15.0, macOS
Catalina, MacBook Air 1.8 GHz i5, 8GB Ram) with default browser settings were
selected. The interaction pattern for the website consisted of six clicks over
27 seconds.

We developed a software bot with the Python programming language to simulate
user interaction using the “PyAutoGUI” package (PyAutoGUI, 2021). The package
enables programmatic access to the mouse and keyboard. Following its
development, we ran the interaction pattern a thousand times in both browsers,
i.e., 2000 recorded user patterns. For each individual user-initiated event
within a pattern, we calculated the delay between a click of the bot and its
recognition by QButterfly (“click time delay”). To get the relevant click
timepoint within the bot, we calculated the arithmetic mean of the timepoint
before and directly after the execution of the Python function to generate the
click. As a proxy for dwell time, we further calculated the intervals between
two consecutive clicks that took the user from one webpage to the next.
Finally, we compared the intervals between the bot and QButterfly (“dwell time
delay”).

####  6.1.2. Results

QButterfly successfully recorded all user actions generated by the bot, i.e.,
no event was missed, and no pattern was recorded in another sequence than
generated. Table 3 and Figure 6 show the results for the two browsers. The
mean delays were generally below 21ms, with only a few outliers. Only one
outlier with more than four standard deviations from the mean (15
milliseconds) was detected for the dwell time delay on Safari. The QButterfly
recordings were precise, with standard deviations between 1.43 and 3.63
milliseconds. For the intended purpose of enabling online user interaction
studies with timings in the range of seconds, this degree of temporal
precision appears to be more than sufficient.

Table 3. Summary of the delays (ms) between the automatic click generated by
the bot and the corresponding QButterfly timestamp. The click time delay was
calculated based on the click events, and the dwell time delay was based on
the time between consecutive click events that brings the user from one page
to the other.

| Click Time Delay (ms) | Dwell Time Delay (ms)
---|---|---
Browser | m | SD | 95% CI | m | SD | 95% CI
Chrome (Win) | 7.88 | 3.63 | [7.66, 8.10] | 4.39 | 3.46 | [4.17, 4.60]
Safari (Mac) | 20.23 | 1.62 | [20.13, 20.33] | 1.80 | 1.43 | [1.71, 1.89]

Figure 6. Box plots of the delays (ms) between the automatic click using the
Python bot and the corresponding QButterfly timestamp. The click time delay
(left) was calculated based on the click events, and the dwell time delay
(right) was calculated based on the time between consecutive click events.

The plot on the left shows the click time delay in ms Chrome (Mean 7) and
Safari (Mean 20). The plot on the right shows the dwell time delay for Chrome
(Mean 4) and Safari (Mean 2)

###  6.2. Field Study

####  6.2.1. Design and Subjects

We performed a privacy-related HCI experiment to monitor user behavior when
confronted with differently designed cookie banners on websites. The purpose
of cookie banners is to inform users about the meaning of tracking and collect
consent. Minor design changes can significantly affect the decision to accept
or decline cookies (Utz et al., 2019). The IRB of our university has confirmed
that no ethical approval was required, and informed consent was obtained from
all individual participants. This study was limited to users with desktop
computers, i.e., subjects with tablets and smartphones were excluded because
the website was designed specifically for desktop screens. Users had to be UK
residents, were recruited from the online panel Prolific, and were paid for
their participation. We employed the “Qualtrics template” described earlier.
After consent and screening, we randomly assigned users to different
experimental conditions with other stimuli. Each website presented a different
type of cookie banner, and users could interact with the banner and the
website after accepting or declining the use of cookies. We recorded page load
events as well as user clicks. At the end of the study, participants had to
pass an attention check. In total, n = 6,045 users completed the experiment,
and each user’s interaction pattern was analyzed. Subjects took a median time
of 4.2 minutes to complete the study.

####  6.2.2. Results

Table 4 shows the characteristics of the subjects’ computers. As these were
restricted to desktop computers only, operating systems, such as Android or
iOS, are not represented. Subjects used a median browser window width of 1440
px (25th percentile: 1366 px; 75th percentile: 1680 px) and height of 864 px
(25th percentile: 768 px; 75th percentile: 1050 px).

Table 4. Computing system characteristics in the field study (n = 6,045) Browser |  | OS
---|---|---
Chrome | 71.1% |  | Windows | 73.3%
Firefox | 10.0% |  | Mac | 24.5%
Safari | 9.3% |  | Linux | 1.6%
Edge | 8.5% |  | ChromeOS | 0.6%
Opera | 1.1% |  | Others | 0.1%

QButterfly worked reliably across the browser types and operating systems, and
of the 6,045 recorded user interaction patterns, only a few showed any
idiosyncrasy (1.3%). Concretely, nineteen respondents had no events recorded,
and 59 recordings had invalid time stamps for events (“undefined”). One of the
affected users provided qualitative feedback and mentioned using a blocking
tool for cross-site scripts333Cross-site scripting is a form of attack where
malicious scripts are injected in an otherwise benign and trusted website
(OWASP, n.d.). In the case of the QButterfly system architecture, Qualtrics
and the stimulus website have different internet addresses. That is why the
QButterfly JavaScript library embedded in the HTML website can be
misinterpreted as a malign cross-site script and blocked if the user has a
blocker installed.. This could explain why these idiosyncrasies occurred in
the first place. The remaining 5,967 recordings were further checked for
plausibility (e.g., chronological order of events, missing events). We
discovered 39 (0.6%) interaction patterns with implausible event orders and
ascertained that these particular user-click events had not been recorded
correctly. This could subsequently be traced back to a mistake in embedding
the QButterfly JavaScript library into the related web page’s HTML code. As a
result, we introduced a function in the JavaScript library to indicate an
incorrect embedding and updated the documentation on the QButterfly website.
Such experiences underline the general importance of conducting pre-studies
before using the library in live studies to ensure full functionality in the
field.

##  7\. Discussion

###  7.1. Contribution

QButterfly contributes to HCI research in the form of a validated, ready-to-
use toolkit and its open-source code (cp. (Fogarty, 2017; Ledo et al., 2018)).
It has been validated via a demonstration (qbutterfly.github.io), usage in two
HCI-related studies ((Ebert et al., 2021, 2022)), and technical measurement
(Section 6). The toolkit addresses several technical challenges researchers
have when they want to conduct controlled online user interaction studies at
scale (Hirth et al., 2017):

  1. (1)

The software may reduce authoring time and complexity because it solves one
major technical challenge, namely the disintegration of required tools (Hirth
et al., 2017). Therefore, it is easier to design and evaluate new interactive
systems at scale with large, crowdsourced participant groups, which is a
demand of many HCI researchers (Egelman et al., 2014; Findlater et al., 2017).
Researchers save time in developing their study infrastructure and the data
analysis after their study.

  2. (2)

It may empower non-tech-savvy researchers to conduct user interaction studies
with limited programming skills without being overwhelmed by existing toolkits
(e.g., psiTurk (Gureckis et al., 2016)). Also, behavioral researchers from
other disciplines (e.g., online marketing) might be enabled to conduct online
studies that would usually require rather sophisticated technical skills
(Hirth et al., 2017).

  3. (3)

QButterfly may facilitate the re-use of existing functionality as it is
aligned with popular survey tools HCI researchers use (i.e., Qualtrics,
Limesurvey) and provides easy access to a rich set of existing and evaluated
functionalities and knowledge (e.g., LimeSurvey MTurk integration). Survey and
experimental features such as scales, quotas, survey flow, or random
assignment of participants are available “off the shelf” and ”via click” in
existing survey tools. Also, very complex experiments with many conditions can
be carried out more quickly if these standard features can be used.

  4. (4)

The toolkit may facilitate the replication of ideas by providing access to a
verified study infrastructure, which enables the comparison among studies.

Scientific research has several advantages when researchers can conduct
studies more quickly and easily. Hypotheses and artifacts can be investigated
iteratively and at an earlier stage, which helps to leave wrong paths sooner.
In addition, less technology-savvy researchers from other disciplines (e.g.,
marketing, consumer behavior, psychology) are more likely to participate in
discussions if the same tools are available.

###  7.2. Limitations and Future Work

The toolkit faces several challenges typical for online studies where users
use their own devices. Occasional idiosyncrasies (e.g., poor internet
connection or specific browser extensions blocking events) can cause losses of
tracking data, but our Excel functions automatically identify these. However,
our validation study (see “Validation of the Software”) suggested that these
issues only affect a small fraction of trials. While we did not observe these
exceptions in our laboratory setup, about one percent of users and their
tracking data were affected when data were collected in an uncontrolled,
crowdsourcing setting. In a conservative approach, these individuals can be
excluded from the study. Although our implementation appears to perform
reliably well across different browsers, it is incompatible with Internet
Explorer. In this case, users can proceed through the questionnaire, but their
tracking data are not recorded. However, the worldwide market share of
Internet Explorer is steadily declining and lies at about 2 percent in 2021
(Kinsta, 2021).

The default instantiation of QButterfly is highly dependent on the survey
platform, and the user influence on the future development of the survey
software is minimal. Therefore, changes in the survey software could cause
QButterfly to stop working and require adjustments to the code. For example,
incompatibility issues led to the discontinuation of QRTEngine – software for
running online reaction time experiments using Qualtrics (Barnhoorn et al.,
2015; van Steenbergen, 2021). We have considered this by making the
integration of QButterfly into the survey platform extremely lightweight.
Instead of a dedicated, tightly integrated program library, very little
JavaScript code is included in the survey template.

In studies using a user’s web browser, users can interact with the displayed
content and other browser elements. In the case of QButterfly, users can press
both the backward/forward navigation button and the browser’s refresh button.
Web developers cannot fully mitigate these user actions and create additional
“ready” and “load” recorded events for the affected stimulus web pages.
However, QButterfly detects when a user presses the backward/forward
navigation buttons and immediately redirects the user to the current page.

Future work could extend the features provided by QButterfly in its current
form. While it was developed with Qualtrics in mind, the code could be readily
adapted to other online survey platforms or custom interfaces, provided they
support custom JavaScript code and event handling as well as the display of
iframes. Furthermore, the functions that handle the analysis of the tracking
data can be ported to a different environment (e.g., R, Python). Currently,
they are implemented in the proprietary software MS Excel in combination with
a VBA script. However, they primarily execute regular expressions to analyze
events (e.g., the expression “[0-9]+#[^;]+;” matches an event), which are easy
to port to different environments.

The package currently only records user-generated keyboard or mouse clicks
because the QButterfly JavaScript library embedded in the website only listens
to these inputs. However, it can be extended to listen to other browser event
types and record those as well (e.g., mouse trajectories generated by the
“mousemove” browser event). The toolkit can also be extended for user cases
requiring higher resolution timing. For example, best practices for stimulus
presentation on the web, such as preloading assets, can be integrated
(Garaizar and Reips, 2019).

###  7.3. Conclusion

We present an open-source HCI toolkit (github.com/QButterfly) that facilitates
controlled online user interaction studies using the widespread Qualtrics and
LimeSurvey platforms. It helps to overcome technical challenges that non-tech-
savvy researchers typically face, such as the disintegration of survey tools
and stimulus material (e.g., a website) and reduces the authoring time for
studies. Scientists can rely on the existing functionality of their survey
tools and only need to add a JavaScript library to their stimulus website to
track a user’s clicks throughout their website. We empirically validated the
software in a laboratory and a field study and have used it in two HCI
studies.

###### Acknowledgements.

We would like to thank the Hasler Foundation and the DIZH initiative of the
Canton of Zurich for their financial support.

## References

  * (1)
  * Acar et al. (2020) Gunes Acar, Steven Englehardt, and Arvind Narayanan. 2020\.  No boundaries: data exfiltration by third parties embedded on web pages.  _Proc. Priv. Enhancing Technol._ 2020, 4 (2020), 220–238.
  * Anwyl-Irvine et al. (2021) Alexander Anwyl-Irvine, Edwin S. Dalmaijer, Nick Hodges, and Jo K. Evershed. 2021.  Realistic precision and accuracy of online experiment platforms, web browsers, and devices.  _Behavior Research Methods_ 53, 4 (Aug. 2021), 1407–1425.  https://doi.org/10.3758/s13428-020-01501-5
  * Anwyl-Irvine et al. (2020) Alexander L. Anwyl-Irvine, Jessica Massonnié, Adam Flitton, Natasha Kirkham, and Jo K. Evershed. 2020\.  Gorilla in our midst: An online behavioral experiment builder.  _Behavior Research Methods_ 52, 1 (Feb. 2020), 388–407.  https://doi.org/10.3758/s13428-019-01237-x
  * Baravalle and Lanfranchi (2003) Andres Baravalle and Vitaveska Lanfranchi. 2003.  Remote Web usability testing.  _Behavior Research Methods, Instruments, & Computers_ 35, 3 (Aug. 2003), 364–368.  https://doi.org/10.3758/BF03195512
  * Barnhoorn et al. (2015) Jonathan S. Barnhoorn, Erwin Haasnoot, Bruno R. Bocanegra, and Henk van Steenbergen. 2015.  QRTEngine: An easy solution for running online reaction time experiments using Qualtrics.  _Behavior Research Methods_ 47, 4 (Dec. 2015), 918–929.  https://doi.org/10.3758/s13428-014-0530-7
  * Bridges et al. (2020) David Bridges, Alain Pitiot, Michael R. MacAskill, and Jonathan W. Peirce. 2020.  The timing mega-study: comparing a range of experiment generators, both lab-based and online.  _PeerJ_ 8 (July 2020), e9414.  https://doi.org/10.7717/peerj.9414 Publisher: PeerJ Inc..
  * Chen et al. (2016) Daniel L Chen, Martin Schonger, and Chris Wickens. 2016\.  oTree—An open-source platform for laboratory, online, and field experiments.  _Journal of Behavioral and Experimental Finance_ 9 (2016), 88–97.
  * Ebert et al. (2022) Nico Ebert, Kurt A. Ackermann, and Angela Bearth. 2022\.  When information security depends on font size: how the saliency of warnings affects protection behavior.  _Journal of Risk Research_ 0, 0 (2022), 1–22.  https://doi.org/10.1080/13669877.2022.2142952
  * Ebert et al. (2021) Nico Ebert, Kurt Alexander Ackermann, and Björn Scheppler. 2021\.  Bolder is Better: Raising User Awareness through Salient and Concise Privacy Notices. In _Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems_ (Yokohama, Japan) _(CHI ’21)_. Association for Computing Machinery, New York, NY, USA, Article 67, 12 pages.  https://doi.org/10.1145/3411764.3445516
  * Egelman et al. (2014) Serge Egelman, Ed H. Chi, and Steven Dow. 2014.  Crowdsourcing in HCI Research.  In _Ways of Knowing in HCI_ , Judith S. Olson and Wendy A. Kellogg (Eds.). Springer New York, New York, NY, 267–289.  https://doi.org/10.1007/978-1-4939-0378-8_11
  * Ferreira et al. (2015) Denzil Ferreira, Vassilis Kostakos, and Anind K. Dey. 2015\.  AWARE: Mobile Context Instrumentation Framework.  _Frontiers in ICT_ 2, 0 (2015), 1–9.  https://doi.org/10.3389/fict.2015.00006
  * Findlater et al. (2017) Leah Findlater, Joan Zhang, Jon E. Froehlich, and Karyn Moffatt. 2017.  Differences in Crowdsourced vs. Lab-Based Mobile and Desktop Input Performance Data. In _Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems_ (Denver, Colorado, USA) _(CHI ’17)_. Association for Computing Machinery, New York, NY, USA, 6813–6824.  https://doi.org/10.1145/3025453.3025820
  * Fogarty (2017) James Fogarty. 2017\.  Code and contribution in interactive systems research. In _Workshop HCITools: Strategies and Best Practices for Designing, Evaluating and Sharing Technical HCI Toolkits at CHI_. Association for Computing Machinery, New York, NY, USA, 1–4.  https://homes.cs.washington.edu/~jfogarty/publications/workshop-chi2017-codeandcontribution.pdf
  * Garaizar and Reips (2019) Pablo Garaizar and Ulf-Dietrich Reips. 2019.  Best practices: Two Web-browser-based methods for stimulus presentation in behavioral experiments with high-resolution timing requirements.  _Behavior Research Methods_ 51, 3 (June 2019), 1441–1453.  https://doi.org/10.3758/s13428-018-1126-4
  * Goldstein (2019) Scott Goldstein. 2019\.  A Novel Technique for A/B Testing Using Static Prototypes.  _Weave: Journal of Library User Experience_ 2, 1 (2019), 1–18.  https://doi.org/10.3998/weave.12535642.0002.101
  * Google (2021) Google. 2021.  _Google Analytics Dashboard_.  Alphabet.  Retrieved September 11, 2021 from https://analytics.google.com
  * Gureckis et al. (2016) Todd M Gureckis, Jay Martin, John McDonnell, Alexander S Rich, Doug Markant, Anna Coenen, David Halpern, Jessica B Hamrick, and Patricia Chan. 2016.  psiTurk: An open-source framework for conducting replicable behavioral experiments online.  _Behavior research methods_ 48, 3 (2016), 829–842.
  * Hasan et al. (2009) Layla Hasan, Anne Morris, and Steve Probets. 2009.  Using Google Analytics to Evaluate the Usability of E-Commerce Sites. In _Human Centered Design_ , Masaaki Kurosu (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 697–706.
  * Hirth et al. (2017) Matthias Hirth, Jason Jacques, Peter Rodgers, Ognjen Scekic, and Michael Wybrow. 2017.  Crowdsourcing Technology to Support Academic Research. In _Evaluation in the Crowd. Crowdsourcing and Human-Centered Experiments_ , Daniel Archambault, Helen Purchase, and Tobias Hoßfeld (Eds.). Springer International Publishing, Cham, 70–95.
  * Jansen (2009) Bernard J. (Jim) Jansen. 2009\.  Understanding User-Web Interactions via Web Analytics.  _Synthesis Lectures on Information Concepts, Retrieval, and Services_ 1, 1 (Jan. 2009), 1–102.  https://doi.org/10.2200/S00191ED1V01Y200904ICR006 Publisher: Morgan & Claypool Publishers.
  * Kelton et al. (2020) Conor Kelton, Jihoon Ryoo, Aruna Balasubramanian, Xiaojun Bi, and Samir R Das. 2020.  Modeling User-Centered Page Load Time for Smartphones. In _22nd International Conference on Human-Computer Interaction with Mobile Devices and Services_ _(MobileHCI ’20)_. Association for Computing Machinery, New York, NY, USA, 1–12.  https://doi.org/10.1145/3379503.3403565
  * Kinsta (2021) Kinsta. 2021.  _Global Desktop Browser Market Share for 2021_.  Kinsta.  Retrieved 2021-08-25 from https://kinsta.com/browser-market-share/
  * Kittur et al. (2008) Aniket Kittur, Ed H. Chi, and Bongwon Suh. 2008.  Crowdsourcing user studies with Mechanical Turk. In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ _(CHI ’08)_. Association for Computing Machinery, New York, NY, USA, 453–456.  https://doi.org/10.1145/1357054.1357127
  * Kohavi and Longbotham (2007) Ron Kohavi and Roger Longbotham. 2007.  Online Experiments: Lessons Learned.  _Computer_ 40, 9 (Sept. 2007), 103–105.  https://doi.org/10.1109/MC.2007.328 Conference Name: Computer.
  * Kohavi and Longbotham (2017) Ron Kohavi and Roger Longbotham. 2017.  Online Controlled Experiments and A/B Testing.  _Encyclopedia of machine learning and data mining_ 7, 8 (2017), 922–929.
  * Lazar et al. (2017) Jonathan Lazar, Jinjuan Heidi Feng, and Harry Hochheiser. 2017.  _Research methods in human-computer interaction_ (second edition ed.).  Morgan Kaufmann, Boston.
  * Ledo et al. (2018) David Ledo, Steven Houben, Jo Vermeulen, Nicolai Marquardt, Lora Oehlberg, and Saul Greenberg. 2018\.  Evaluation Strategies for HCI Toolkit Research. In _Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems_ (Montreal QC, Canada) _(CHI ’18)_. Association for Computing Machinery, New York, NY, USA, 1–17.  https://doi.org/10.1145/3173574.3173610
  * Mathur and Reichling (2019) Maya B. Mathur and David B. Reichling. 2019.  Open-source software for mouse-tracking in Qualtrics to measure category competition.  _Behavior Research Methods_ 51, 5 (Oct. 2019), 1987–1997.  https://doi.org/10.3758/s13428-019-01258-6
  * Nielsen and Pernice (2009) Jakob Nielsen and Kara Pernice. 2009.  _Eyetracking Web Usability_ (1st ed.).  New Riders Publishing, USA.
  * Optimizely (2021) Optimizely. 2021\.  _Unlock digital potential_.  Optimizely.  Retrieved 2021-08-19 from https://www.optimizely.com
  * Oulasvirta and Hornbæk (2016) Antti Oulasvirta and Kasper Hornbæk. 2016.  HCI Research as Problem-Solving. In _Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems_ (San Jose, California, USA) _(CHI ’16)_. Association for Computing Machinery, New York, NY, USA, 4956–4967.  https://doi.org/10.1145/2858036.2858283
  * PyAutoGUI (2021) PyAutoGUI. 2021\.  _Welcome to PyAutoGUI’s documentation! — PyAutoGUI documentation_.  PyAutoGUI.  Retrieved 2021-10-28 from https://pyautogui.readthedocs.io/en/latest/
  * Stroop (1935) J Ridley Stroop. 1935\.  Studies of interference in serial verbal reactions.  _Journal of experimental psychology_ 18, 6 (1935), 643\.
  * Tang et al. (2010) Diane Tang, Ashish Agarwal, Deirdre O’Brien, and Mike Meyer. 2010.  Overlapping experiment infrastructure: more, better, faster experimentation. In _Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining_ _(KDD ’10)_. Association for Computing Machinery, New York, NY, USA, 17–26.  https://doi.org/10.1145/1835804.1835810
  * Utz et al. (2019) Christine Utz, Martin Degeling, Sascha Fahl, Florian Schaub, and Thorsten Holz. 2019.  (Un)informed Consent: Studying GDPR Consent Notices in the Field. In _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ _(CCS ’19)_. Association for Computing Machinery, London, United Kingdom, 973–990.  https://doi.org/10.1145/3319535.3354212
  * van Steenbergen (2021) Henk van Steenbergen. 2021\.  _QRTEngine An Easy Solution for Running Online Reaction Time Experiments Using Qualtrics_.  QRTEngine.  Retrieved 2021-08-25 from http://www.qrtengine.com/
  * W3C (2022) W3C. 2022.  _HTML iframe tag_.  W3C.  Retrieved 2022-08-11 from https://www.w3schools.com/tags/tag_iframe.ASP


# AutoGraph: Predicting Lane Graphs
from Traffic Observations

Jannik Zürn1, Ingmar Posner2, and Wolfram Burgard3 Manuscript received: June
27, 2023; Revised: October 4, 2023; Accepted: November 3, 2023. This paper was
recommended for publication by Editor Cesar Cadena Lerma upon evaluation of
the Associate Editor and Reviewers’ comments.This work was supported under DFG
grant number BU 865/10-21Jannik Zürn is with the Faculty of Engineering,
University of Freiburg, 79115 Freiburg, Germany<EMAIL_ADDRESS>freiburg.de2Ingmar Posner is with the Applied AI Lab, Oxford University,
Oxford, UK, supported by a UKRI/EPSRC Programme Grant [EP/V000748/1]3Wolfram
Burgard is with the Department of Engineering, University of Technology
Nuremberg, Nuremberg, GermanyDigital Object Identifier (DOI): see top of this
page.

###### Abstract

Lane graph estimation is a long-standing problem in the context of autonomous
driving. Previous works aimed at solving this problem by relying on large-
scale, hand-annotated lane graphs, introducing a data bottleneck for training
models to solve this task. To overcome this limitation, we propose to use the
motion patterns of traffic participants as lane graph annotations. In our
AutoGraph approach, we employ a pre-trained object tracker to collect the
tracklets of traffic participants such as vehicles and trucks. Based on the
location of these tracklets, we predict the successor lane graph from an
initial position using overhead RGB images only, not requiring any human
supervision. In a subsequent stage, we show how the individual successor
predictions can be aggregated into a consistent lane graph. We demonstrate the
efficacy of our approach on the UrbanLaneGraph dataset and perform extensive
quantitative and qualitative evaluations, indicating that AutoGraph is on par
with models trained on hand-annotated graph data. Model and dataset will be
made available at http://autograph.cs.uni-freiburg.de/.

###### Index Terms:

Deep Learning for Visual Perception, Computer Vision for Transportation,
Semantic Scene Understanding

##  I Introduction

Autonomous vehicles require detailed knowledge about their surroundings to
safely and robustly navigate complex environments. Most approaches to
automated driving follow one of the two major paradigms: map-based or mapless
driving. Map-based approaches typically rely on HD maps entailing detailed
geospatial information relevant to driving tasks, including the positions of
traffic lights, lanes, or street crossings. In this context, the graph of lane
centerlines (i.e. the lane graph) is a crucial component that encodes the
position and connectivity of all lanes. A major bottleneck in deploying map-
based autonomous driving approaches is the slow and expensive manual
annotation process to generate HD maps for all regions where the vehicle is
intended to operate. Methods capable of estimating the lane graphs robustly in
an automated fashion are crucial for scaling up the areas covered by HD maps
[15, 30, 3]. Mapless driving approaches, in contrast, solely rely on onboard
sensor measurements to infer the position and layout of objects and surfaces
relevant to the driving task, including the position and orientation of roads
and lanes. For mapless driving, the accurate and robust estimation of the
spatial and topological lane layout in the vicinity of the vehicle is
paramount for safe and efficient navigation. Therefore, automatic lane graph
estimation is a crucial task in map-based and mapless automated driving.

Prior work in lane graph estimation focuses on training models under full
supervision [3, 30, 14], relying on large-scale ground-truth lane graph
annotations, typically obtained from a large number of human annotators. The
production of accurate annotations such as those available as part of the
Argoverse2 [22] and NuScenes [4] datasets is, therefore, resource-intensive in
both money and time.

Figure 1: Our approach AutoGraph leverages vehicle tracklets and predicts
complex lane graphs from aerial images without requiring any hand-annotated
lane graphs for supervision.

Inspired by the success of vehicle tracking approaches [17, 9, 20] and by
prior work in the context of automatic annotation from traffic participants
[1, 31], in this work, we propose to leverage traffic participant tracklets as
the only annotation source for lane graph estimation and do not require any
manually obtained graph annotations. Most traffic participants follow their
respective lanes with high accuracy. Aggregated over large numbers, the
trajectories of traffic participants encode the overall structure of lane
graphs well (see Fig. 1). We interpret this driving data as a data source for
the annotation of lane graphs. In our approach, AutoGraph, we track traffic
participants in challenging urban environments and propose a novel tracklet
merging scheme, allowing us to formulate a supervised learning task in which
we leverage aerial images as input and the merged tracklets serve as the
learning target for our model. The overall approach is capable of accurately
predicting lane graphs covering large areas with high accuracy while the
pipeline does not require any hand-annotated data.

To summarize, this work makes the following contributions:

  * •

a novel tracklet aggregation scheme leveraging observed traffic participant
tracklets as annotation sources for lane graph estimation models;

  * •

the large-scale UrbanTracklet dataset with hundreds of thousands of vehicle
and pedestrian tracklets generated from the Argoverse2 and UrbanLaneGraph
datasets;

  * •

and extensive qualitative and quantitative ablation studies on the
UrbanLaneGraph dataset, demonstrating the efficacy of our approach.

##  II Related Works

##### Lane Graph Estimation

Over the past years, the task of lane graph estimation has gained much
attention in the autonomous driving research community. In contrast to road
graph estimation, where the goal is to estimate the connectivity between roads
[2, 19], lane graph estimation entails predicting the position of lanes and
how they are connected. This task is much more challenging, in particular in
areas with complex lane connections such as roundabouts or multi-arm
intersections. Homayounfar _et al._ [15] predict the lane graph of highway
scenes with an iterative RNN model from projected LiDAR data. Zürn _et al._
[30] proposed a Graph R-CNN-based model for lane graph estimation from
aggregated LiDAR data in urban scenes. He _et al._ [14] leverage a multi-stage
approach for lane graph extraction in which they first extract straight road
sections between intersections and subsequently learn the connectivity between
each incoming and outgoing lane arm. Büchner _et al._ [3] proposed a bottom-up
approach for lane graph estimation. They first estimate the successor graph
from a given starting position using a graph neural network and subsequently
aggregate a full lane graph by iteratively merging each successor graph into a
global one. Similar to our work in spirit, Karlsson _et al._ [16] infer
maximum likelihood lane graphs from traffic observations with a directional
soft lane probability model. They evaluate their model on the NuScenes
dataset. However, they do not consider model inference from aerial images but
from aggregated onboard sensor measurements. Crucially, and in contrast to our
approach, their model is not capable of estimating large lane graphs due to
the non-iterative nature of their approach.

While the aforementioned works show promising results in challenging
environments, most of them require large-scale handcrafted graph annotations
or cannot generate predictions for large-scale scenes. In the approach
presented here, we do not require any manual annotations and instead leverage
data encoded in the behavior of observed traffic participants.

##### Trajectory Prediction

Our successor lane graph prediction module is related to the task of
trajectory prediction. From the large body of literature available in this
field we briefly review the most relevant recent related works. Most
approaches condition their models on rasterized or vectorized HD map
representations [5, 27, 10], discrete graphs [18] or aerial images [28]. In
Chai _et al._ [5], future vehicle positions are encoded by estimating the
distribution over future trajectories for each agent while Zhao _et al._ [27]
leverage a three-stage approach that finds prediction targets, estimates
future motion for each, and scores each predicted trajectory to yield the
final motion prediction. Our work also shares similarities with the line of
work by Gilles  _et al._ [11, 12, 13]. They frame the trajectory prediction
task as a heatmap regression task, where an HD map representation is used for
prediction conditioning. After subsequent post-processing of this heatmap,
they sample future agent trajectories. In contrast to most existing works, we
refrain from leveraging an HD map representation and instead solely rely on
aerial images for our prediction task. In addition to regressing future
possible agent positions, we also use this prediction block as input for a
graph aggregation module to learn a complete lane graph of a given input
image.

##### Automatic Annotations in Autonomous Driving

There exists a sizable body of work that considers the data encoded either in
the driving behavior of the ego-vehicle or of other traffic participants.
Barnes _et al._ [1] use the ego-trajectory of a vehicle to annotate drivable
regions in an image. They project their own future positions into the current
camera image to label pixels as drivable. Other works in self-supervised
learning for navigation [21, 29] also use the ego-trajectory to label pixels
for a vision-based ground classifier. Tracklets have been used by multiple
previous works in the context of autonomous driving tasks. Zürn _et al._ [31]
used the trajectories of other traffic participants such as vehicles and
pedestrians, obtained from a LiDAR tracker, to annotate ground surfaces in
urban environments. Other works also explored the benefits of inferring
driving policies from the behavior of other traffic participants [23, 25, 6].
Chen _et al._ [6] leverage driving experiences collected from the ego vehicle
and other vehicles jointly to train a driving policy from real-world data.
Recent work by Collin _et al._ [8] proposes an automated system for
aggregating observed traffic participant tracklets into a lane graph
representation. While their work shows a good performance in dense traffic
scenarios, it does not generalize to unseen areas since their approach does
not involve training a model on this data.

##  III Technical Approach

Our approach proceeds in three steps. In the first step, denoted tracklet
parsing and merging, we track traffic participants through all scenes in the
dataset and prepare the data for model training. In the subsequent model
training step, we train the proposed model with data obtained in the first
stage. In the third step, we perform inference with our trained model to
perform graph exploration and aggregation into a globally consistent
representation. In the following, we describe each step in detail.

Figure 2: Visualization of tracklets in the city of Austin, Texas, aligned
with aerial imagery (darkened for better contrast).

###  III-A Tracklet Parsing and Merging

In the following, we describe our tracklet parsing and merging pipeline. We
start our data processing pipeline by tracking traffic participants from ego-
vehicle data in all available scenes of the Argoverse2 dataset [22] across all
six available cities. Each scene in the dataset consists of approximately 20
seconds of driving. For each scene, we track vehicles such as cars, trucks,
motorcycles, and busses using a pre-trained LiDAR-based object detector [20]
that processes the vehicle onboard LiDAR point clouds. We note that the
performance of the tracker predictions may affect the quality of the
annotations and thus the downstream performance of our approach. We transform
all tracklets into a global coordinate frame. Subsequently, we smooth the
tracklets with a moving average filter to minimize the amount of observation
noise and the influence of erratic driving behavior (i.e., steering
inaccuracies).

Fig. 2 illustrates an exemplary urban scene with the observed vehicle
tracklets. Due to imperfect vehicle driving manoeuvres and the inherent
observation noise, tracklets of observed traffic participants do not perfectly
overlap with the ground-truth lane graph. Furthermore, and more importantly,
each tracklet only covers a subset of the actual lane graph since the
corresponding vehicle was only visible from the ego vehicle for a few seconds.
Thus, the goal of the tracklet merging module is to merge tracklets that have
significant overlap and follow the same underlying lane segment with a high
likelihood.

In the following, we describe the tracklet merging procedure. We define a
tracklet $\mathbf{T}$ as a list of points $\mathbf{p}_{t}\in\mathbb{R}^{2}$
describing the 2D position of a tracked object centroid at the tracking time
step $t$ and a list of heading vectors $\mathbf{h}_{t}\in\mathbb{R}^{2}$
describing the heading of the tracked object. The tracking frequency is
constant for all tracklets and equals the LiDAR frequency. We define the set
of all object positions in all tracklets as $\mathcal{P}$. Our goal is to
merge multiple tracklets into a successor graph that encompasses all regions
that have been traversed by tracked vehicles which passed through a given
starting position. To this end, we define an Euclidean distance tracklet
merging matrix $\mathbf{M}_{D}$ and an angle-based merging matrix
$\mathbf{M}_{A}$. The Euclidean distance merging matrix $\mathbf{M}_{D}$ is
defined as the element-wise Euclidean distance of two object centroids:

$M_{D,ij}=||\mathbf{p}_{i}-\mathbf{p}_{j}||_{2}^{2},$ (1)

where $\mathbf{M}_{D}\in\mathbb{R}^{|\mathcal{P}|\times|\mathcal{P}|}$. We
also define an angle matrix
$\mathbf{M}_{A}\in\mathbb{R}^{|\mathcal{P}|\times|\mathcal{P}|}$, indicating
the absolute relative angle between object heading $\mathbf{h}_{i}$ and
$\mathbf{h}_{j}$:

$M_{A,ij}=\big{|}\arccos{\Big{(}\frac{\mathbf{h}_{i}\cdot\mathbf{h}_{j}}{|\mathbf{h}_{i}|\cdot|\mathbf{h}_{j}|}\Big{)}}\big{|}.$
(2)

To merge multiple tracklets into a successor graph, we define a binary
tracklet merging matrix
$\mathbf{M}\in\\{0,1\\}^{|\mathcal{P}|\times|\mathcal{P}|}$ as follows:

$\mathbf{M}:=[\mathbf{M}_{D}<d_{max}]\land[\mathbf{M}_{A}<\alpha_{max}],$ (3)

where $M_{ij}=1$ implies a merging of the tracklet containing $\mathbf{p}_{i}$
with the tracklet containing $\mathbf{p}_{j}$. So far, we only considered the
relative heading angle and relative position of two tracked objects. In the
final step, we update $\mathbf{M}$ and integrate all recorded tracklets into
the connectivity matrix. Since each single tracklet consists of a list of
observed object positions and headings, we add all pairs of consecutive object
positions and headings in each tracklet to $\mathbf{M}$ as well. Note that a
connection $p_{i}\rightarrow p_{i+1}$ encoded in a specific tracklet adds the
respective connection in $\mathbf{M}[i,i+1]$ but does not add the connection
in $\mathbf{M}[i+1,i]$ since each tracklet has a notion of direction. Thus,
$\mathbf{M}\neq\mathbf{M}^{T}$ in the general case.

Using this formulation, we now have a mechanism for generating a successor
graph $\mathcal{S}_{q}$ from a query point $\mathbf{q}$ by following all
tracklets connected to $\mathbf{q}$ according to $\mathbf{M}$. In order to fit
our model to this data, we randomly select a query point $\mathbf{q}$ from the
aerial image and extract a small image crop around $\mathbf{q}$. We extract
all tracklets visible in this crop and extract the successor graph
$\mathcal{S}_{q}$. For an exemplary visualization of the merging procedure,
please refer to Fig. 3.

Furthermore, we extract the Drivable map layer and the Angles map layer. In
these layers, we collect all tracklets of the whole city and colorize all
pixels that are covered by a tracklet as 1 for the Drivable map layer or as
the tracklet angle $\alpha$, for the Angles layer. The remaining pixels are
assigned a value of 0. For visualization of these map layers, please refer to
Fig. 4.

Figure 3: A T-junction with vehicle tracklets (blue dashed lines). Merging
points for tracklets are indicated with a green checkmark while exemplary
failed merges are indicated with a red cross. The extracted successor graph is
visualized in white. Figure 4: Illustration of our successor graph prediction
approach. We first place a virtual agent on a crop of an aerial image. We
first predict the Drivable and Angles map layers from the aerial image crop
with a fully convolutional neural network. We subsequently predict the
successor lane heatmap from the aerial image crop, the predicted drivable
surface, and lane angles. The successor lane heatmap is post-processed into a
successor graph, encoding the location of successor lanes and lane split
points that are reachable from the current agent’s position.

###  III-B Model Training

After our aggregation step, we are able to query all tracklets that are
visible in an aerial image crop, starting from a given querying position
$\mathbf{q}$. To obtain a training dataset for our models, for each query pose
$\mathbf{q}$, we extract an aerial image crop $RGB_{\mathbf{q}}$ from the full
aerial image, centered and oriented around the query pose. In the same way, we
crop the drivable map, producing $D_{\mathbf{q}}$, and the angle map,
producing $A_{\mathbf{q}}$. The whole training pipeline is visualized in Fig.
4. Our model consists of two sub-networks. We train a DeepLabv3+ model [7] to
predict the pixel-wise drivable and angle maps from an RGB aerial image input,
using $D_{\mathbf{q}}$ and $A_{\mathbf{q}}$ as the learning targets. We denote
this model as TrackletNet. This initial task is identified as an auxiliary
task, leveraging the vast amount of tracklets readily available for a given
crop. For training, we use a binary cross-entropy loss to guide the prediction
of the drivable map layer and a mean squared error loss for the prediction of
the angle map. We encode the Drivable layer as a tensor
$D_{ij}\in\\{0,1\\}^{H\times W}$. To circumvent the discontinuous angles at
the singularity $\alpha=\pm\pi$, we encode the angle at pixel location $(i,j)$
as a value pair $[\sin(\alpha),\cos(\alpha)]^{T}$, producing the Angles layer
$A^{k}_{ij}\in\mathbb{R}^{H\times W\times 2}$. To summarize, during the
TrackletNet training stage, we minimize the following loss:

$\mathcal{L}=\frac{1}{HW}\sum_{i<H}\sum_{j<W}\Big{(}D_{ij}\log\hat{D}_{ij}+\alpha\sum_{k}||A^{k}_{ij}-\hat{A}^{k}_{ij}||_{2}^{2}\Big{)},$
(4)

with a weighing factor $\alpha$ between the drivable surface classification
and the angle regression. In our experiments, we set $\alpha=1$.

Subsequently, we train a separate DeepLabv3+ model [7] to predict the
successor graph from pose $\mathbf{q}$, which we parameterize as a heatmap
$\mathbf{S}_{\mathbf{q}}$. To account for the additional Drivable and Angles
input layers, which we feed into this model in addition to the RGB aerial
image crop, we adapt the number of input layers of the model. We denote this
model as SuccessorNet. To obtain per-pixel labeling of the successor graph in
the image crop, we render the successor graph $\mathcal{S}_{q}$ as a heatmap
in the crop by drawing along the graph edges with a certain stroke width. This
heatmap highlights all regions in the aerial image that are reachable by an
agent placed at pose $\mathbf{q}$. We train our SuccessorNet model with a
binary cross-entropy loss. Finally, we skeletonize the predicted heatmap
$\mathcal{\hat{S}}_{q}$ using a morphological skinning process [26] and
convert the skeleton into a graph representation.

###  III-C Graph Exploration and Aggregation

The approach described in the previous sections is capable of inferring the
graph structure of the successor graph from a given query position. In this
section, we illustrate how a complete lane graph can be obtained by running
our AutoGraph model iteratively on its own predictions and by subsequently
aggregating these predictions into a globally consistent graph representation.

To this end, we leverage a depth-first exploration algorithm: We initialize
our model by selecting start poses, which can either be chosen manually or
obtained from our TrackletNet model. We predict the successor graph from this
initial position and repeatedly query our model along the successor graph. In
the case of a straight road section, for each forward pass of our model, we
add a single future query pose to the list of query poses to process. If a
lane split is encountered, for each of the successor subgraphs starting at
lane splits, we add a query pose to the list. If a lane ends or no successor
graphs are found, the respective branch of the aggregated lane graph
terminates and we query the next pose in the list. The exploration terminates
once the list of future query poses is empty. In contrast to prior work [3],
where they aggregate the complete set of successor graphs according to an
elaborate graph aggregation scheme, we instead only add graph nodes to the
global graph where the virtual agent was placed at a given time. Therefore, we
add edges between graph nodes according to the movement of the successor graph
query position. This aggregation formulation simplifies the graph aggregation
scheme since the number of nodes to integrate into the global graph is greatly
reduced.

TABLE I: Comparison of two baseline models with our AutoGraph approach for the Successor-LGP task. We evaluate on the test split of the UrbanLaneGraph dataset. Best model results are marked in bold. Model |  APLS $\uparrow$ |  IoU $\uparrow$ |  TOPO P/R $\uparrow$ |  GEO P/R $\uparrow$ |  SDA${}_{20}\uparrow$ |  SDA${}_{50}\uparrow$ | Human supervision
---|---|---|---|---|---|---|---
LaneGraphNet [30] |  0.179 |  0.063 |  0.0 / 0.0 |  0.0 / 0.0 |  0.0 |  0.0 | ✓
LaneGNN [3] |  0.202 |  0.347 |  0.600 / 0.699 |  0.599 / 0.695 |  0.227 |  0.377 | ✓
AutoGraph (ours) |  0.310 |  0.233 |  0.412 / 0.628 |  0.422 / 0.601 |  0.159 |  0.678 | ✗

##  IV Dataset

We evaluate our proposed method on a large-scale dataset for lane graph
estimation from traffic participants. We use the RGB aerial images and the
ground-truth lane graph annotations from the UrbanLaneGraph dataset [3]. To
obtain the traffic participant tracklets, we leverage the LiDAR dataset split
of the Argoverse2 [22] dataset. The dataset contains consecutive LiDAR scans
for hundreds of driving scenarios. A single driving scenario entails approx.
$20\text{\,}\mathrm{s}$ of real-world driving. We leverage the OpenPCDet [20]
detection and tracking suite for LiDAR point clouds with a CenterPoint [24]
model, pre-trained on the NuScenes dataset [4]. We track the vehicle classes
of Car, Bus, Trailer, and Motorcycle. Subsequently, we transform the
respective LiDAR-centric tracklet coordinates to a global reference frame that
is aligned with the aerial image coordinates. We smooth each tracklet with a
mean filter approach to account for sensor noise and tracking inaccuracies. We
call our tracklet dataset the UrbanTracklet dataset and make it publicly
available as an addition to the UrbanLaneGraph dataset [3]. In Tab. II, we
list all relevant metrics of our UrbanTracklet dataset. In total, our dataset
entails tracklets with an accumulated total length of approximately
$12\,000\text{\,}\mathrm{k}\mathrm{m}$.

Graph Annotation |
---|---
AutoGraph-GT |
AutoGraph |
Figure 5: Qualitative results of our models for the Successor-LGP task. We visualize the successor heatmap and the graph generated from it for our human-supervised model AutoGraph-GT and our tracklet-supervised model AutoGraph. TABLE II: Key statistics of our UrbanTracklet dataset City | Number of tracklets | Total tracklet length
---|---|---
Austin, TX | 287,306 | $3.642\text{\,}\mathrm{k}\mathrm{m}$
Detroit, MI | 73,232 | $1.099\text{\,}\mathrm{k}\mathrm{m}$
Miami, FL | 283,641 | $3.312\text{\,}\mathrm{k}\mathrm{m}$
Palo Alto, CA | 82,351 | $1.050\text{\,}\mathrm{k}\mathrm{m}$
Pittsburgh, PA | 34,505 | $1.390\text{\,}\mathrm{k}\mathrm{m}$
Washington D.C. | 121,557 | $1.469\text{\,}\mathrm{k}\mathrm{m}$
All | 882,592 | $11.962\text{\,}\mathrm{k}\mathrm{m}$

##  V Experimental Results

###  V-A Implementation Details

The TrackletNet and SuccessorNet have identical DeepLabv3+ architectures. The
TrackletNet receives an RGB input image of shape $H\times W\times 3$ and
outputs the Drivable and Angles layer map output. We use two separate decoders
to produce the outputs. The drivable area segmentation has a resolution of
$H\times W$ while the lane angle output has the size of $H\times W\times 2$.
The training data used to train the two models is obtained from the dataset
described in Sec. IV. We crop image segments of size
$$256\text{\,}\mathrm{p}\mathrm{x}$\times$256\text{\,}\mathrm{p}\mathrm{x}$$
from the global aerial image. The crops are oriented along a randomly sampled
tracklet at the bottom centre of each crop. To increase the efficacy of our
aggregation method (see Sec. III-C), we require the successor graph prediction
to be robust w.r.t. perturbations in the position of the virtual agent. To
provide more diverse samples with different positional variations, we randomly
rotate the crop with an angle $\Delta\phi\sim\pazocal{U}(-\pi/3,\pi/3)$.

Using this sampling method, a vast amount of samples can be generated since
the aerial image can be cropped at arbitrary locations and orientations. For
our experiments, we generate a total number of $1.5\text{\,}\mathrm{M}$
samples from all cities combined. We found that the lane graph complexity
differs between different scenes, i.e., straight road sections have much
simpler successor graphs than entries to roundabouts or multi-arm
intersections. We found that a balanced mix between easy (successor graph has
no splits) and hard (successor graph has one or more splits) samples is
beneficial.

TABLE III: Ablation study with multiple model variants for the Successor-LGP task. We compare our AutoGraph model with our human-supervised model variant AutoGraph-GT and evaluate the influence of different map input layers on the model performance. We highlight the best-performing model with and without human supervision, respectively, in bold. Model |  APLS $\uparrow$ |  IoU $\uparrow$ |  SDA${}_{20}\uparrow$ |  SDA${}_{50}\uparrow$ | Human supervision |  Tracklet-Joining |  Drivable map layer |  Angles map layer
---|---|---|---|---|---|---|---|---
AutoGraph-no-join |  0.344 |  0.232 |  0.052 |  0.498 | ✗ |  ✓ |  ✗ |  ✗
AutoGraph |  0.310 |  0.233 |  0.159 |  0.678 | ✗ |  ✗ |  ✗ |  ✗
AutoGraph+D |  0.349 |  0.230 |  0.063 |  0.510 | ✗ |  ✓ |  ✓ |  ✗
AutoGraph+DA |  0.346 |  0.211 |  0.080 |  0.447 | ✗ |  ✓ |  ✓ |  ✓
AutoGraph-GT |  0.377 |  0.281 |  0.048 |  0.416 | ✓ |  N/A |  ✗ |  ✗
AutoGraph-GT+D |  0.418 |  0.268 |  0.072 |  0.418 | ✓ |  N/A |  ✓ |  ✗
AutoGraph-GT+DA |  0.409 |  0.269 |  0.059 |  0.463 | ✓ |  N/A |  ✓ |  ✓

###  V-B Tasks

Following Büchner  _et al._ [3], we evaluate our approach on two complementary
tasks: Successor Lane Graph Prediction (Successor-LGP), and Full Lane Graph
Prediction (Full-LGP). In Successor-LGP, we aim at predicting a feasible ego-
reachable successor lane graph from the current pose of the virtual agent. In
the task of Full-LGP, we compare the complete lane graph in a local region to
the ground-truth graph. We evaluate each task on the test images of the
UrbanLaneGraph dataset [3], which are not used for model training at any
stage. For model evaluation, we use the metrics proposed by Büchner  _et
al._[3].

###  V-C Baselines

To provide relevant comparisons and ablations demonstrating the efficacy of
our AutoGraph approach, we compare it with a baseline model trained on ground-
truth graph annotations, denoted as AutoGraph-GT. For this model, we use the
ground-truth lane graph in places where we would otherwise query the recorded
vehicle tracklets in our AutoGraph approach. This approach yields the ground
truth lane graphs and successor lane graphs according to the graph annotations
available in the dataset. The ground-truth lane graph annotations have none of
the shortcomings of tracklet-based approaches, such as observation noise or
erratic driving behaviour. We also compare to the previously proposed models
LaneExtraction [14] and LaneGNN [3]. Note that other recent works by Colling
_et al._ [8] and Karlsson _et al._ [16] are relevant works but do not aim at
solving the task this work is concerned with and thus cannot be used for
comparison.

###  V-D Task Evaluation

We evaluate our model on two tasks for lane graph estimation: Successor Lane
Graph Prediction and Full Lane Graph Prediction.

####  V-D1 Successor Lane Graph Prediction

We evaluate the performance of our AutoGraph model and compare it with the
recently proposed LaneGNN [30] and LaneGraphNet [3] models. Tab. I lists the
model performances on the test split of the UrbanLaneGraph dataset. Our
experiments indicate that the performance of our AutoGraph model is superior
to the LaneGraphNet model in all metrics and is mostly on par with the
recently proposed LaneGNN model. While it performs much better in the APLS and
SDA50 metric than the LaneGNN model, it is slightly inferior for the TOPO/GEO
metrics and the Graph IoU metric. We hypothesize that the performance of our
AutoGraph model could be further improved in scenes with road occlusions due
to congested roads and overarching vegetation since our model struggles to
predict accurate successor graphs in these regions. Specific treatment of such
scenes in the model training schedule (i.e., active learning) might be
beneficial.

Additionally, we perform ablation studies of multiple variants of our
AutoGraph approach. The results are listed in Tab. III. In our AutoGraph-no-
join variant, we do not join the tracklets (see Sec. III-A), ignoring their
proximity and their relative angles. Instead, we follow tracklets until they
end or until they leave the image crop. We also do not use the Drivable (D)
and Angles (A) model outputs but feed the aerial image directly into the
SuccessorNet model. For our AutoGraph model variant, we use joined tracklets
as per Sec. III-A but omit the TrackletNet auxiliary network. For our
AutoGraph+D and AutoGraph+DA model variants, we add the Drivable and Angles
model outputs, respectively. The model variant AutoGraph-GT does not use the
tracklets of other traffic participants but is trained on ground truth human
graph annotations, where we encode the successor graph as a heatmap instead of
the raw graph representation as in the LaneGNN or LaneGraphNet models.

(a) Washington, D.C. (b) Miami, detail view

Figure 6: Qualitative results on the Full-LGP task. We visualize predictions
of our aggregated AutoGraph in pink color. Our aggregation scheme is capable
of traversing challenging urban scenes featuring complex graph topologies with
high accuracy.

Our ablation studies indicate that the AutoGraph-no-join method overall
performs worse than our AutoGraph model variant. This indicates that joining
tracklets to form more complete successor graphs helps produce higher-quality
and more consistent annotations. Furthermore, the inclusion of the Drivable
map layer on top of the RGB layer improves model performance for some metrics.
Adding the Angles map layer in addition to the Drivable layer does not
consistently improve our evaluation metrics any further. Despite the
additional information that is available about the scene if the Angles map
layer is included, the increased noise produced by imprecise angle estimates
seems to outweigh the benefits of having additional information available.
This result supports the results discussed in Zürn  _et al._ [30], where
additional input modalities did not significantly improve model performance.
For our subsequent experiments, we opted to keep our Drivable and Angles model
components despite the inconclusive results since drivable and angles maps are
a useful model output for potential downstream tasks. Exemplarily, these
outputs could also be aggregated and used to obtain a robust pixel-wise
estimate for the prediction of drivable surface and lane orientation in large
areas, similar to how we aggregate our successor graphs into a large graph
structure.

For qualitative evaluation, we visualize predictions of our best-performing
model in Fig. 5 and the reference model AutoGraph-GT. We observe that both
models are capable of modeling the multimodal spatial distribution of
successor lanes efficiently. However, the AutoGraph-GT model shows more
accurate heatmap outputs, since the annotations used for training stem from
the ground-truth successor lane graph.

To summarize, our experiments demonstrate that our AutoGraph model variants
(trained on tracklets) perform overall similarly to our AutoGraph-GT model
variants (trained on human lane graph annotations), indicating that vehicle
tracklets recorded from a moving recording platform are suitable for training
lane graph prediction models. In the APLS metric and the Graph IoU, the
AutoGraph-GT model variant performs better than the AutoGraph model,
presumably due to the higher annotation accuracy due to the better alignment
of annotation with aerial images.

####  V-D2 Full Lane Graph Prediction

For the Full Lane Graph Prediction task, we initialize our model on 10 initial
poses per evaluation tile and run our aggregation scheme. We compare the
performance of our best-performing model variant with the prediction results
of LaneExtraction [14] and the aggregation module of LaneGNN [3]. Note that
the number of initialization poses is much smaller compared to the number of
initialization poses used for the LaneGNN model [3]. The results are listed in
Tab. IV. We observe that for some metrics, our AutoGraph model achieves
comparable or better performance than the human-supervised LaneGNN [3] or
LaneGraphNet models [30]. Our model performs worse in the TOPO and GEO
metrics. We note that our AutoGraph model struggles with road surface
occlusions introduced by overarching vegetation. However, we emphasize that
since our model uses fewer model initialization poses compared to LaneGNN [3],
a degradation in graph connectivity may be expected since lane graph regions
in occluded areas may not be reached with an iterative aggregation scheme when
no successor graph is found in a given frame.

Our qualitative evaluations show a high graph fidelity, recognizing most of
the visible lanes and modelling their connectivity accurately. Fig 6
illustrates two exemplary lane graphs for the cities of Washington, D.C., and
Miami. We observe that our approach is capable of accurately reconstructing
the lane graph in visually challenging environments. Large scenes with
multiple blocks are handled well and clearly reflect the underlying lane graph
topology. The detailed view of a complex intersection in Miami illustrates
that almost all major intersection arms are covered even in the presence of
visual clutter such as water, boats, parking lots, and asphalt-colored roofs
of buildings. Minor inaccuracies are produced at the five-armed intersection
at the bottom of the aerial image, where not all connections between
intersection arms are present in the inferred lane graph.

TABLE IV: Evaluation on the Full-LGP task. Model |  APLS |  IoU |  TOPO P/R |  GEO P/R
---|---|---|---|---
LaneExtraction [14] |  0.072 |  0.213 |  0.405 / 0.507 |  0.491 / 0.454
LaneGNN [3] |  0.103 |  0.384 |  0.481 / 0.670 |  0.649 / 0.689
AutoGraph |  0.258 |  0.189 |  0.503 / 0.529 |  0.503 / 0.351

##  VI Conclusion

In this work, we presented a novel method for lane graph estimation in urban
environments from traffic participant tracklets. We showed that our model,
which is trained solely on data from tracked vehicles, is capable of
predicting highly accurate lane graphs. We presented a tracklet processing
scheme that allows us to use the observed tracklets of traffic participants as
an annotation source to train our model. We demonstrated the efficacy of our
approach on a large-scale lane graph dataset for which our approach
demonstrated performance close to a ground-truth supervised baseline model.
Future work will address adding pedestrians and bicycle tracklets to the
approach for capturing more diverse annotations. Additionally, the improved
handling of occluded roads appears to be a promising direction for future
research.

## References

  * [1] Dan Barnes, Will Maddern, and Ingmar Posner.  Find your own way: Weakly-supervised segmentation of path proposals for urban autonomy.  In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 203–210. IEEE, 2017.
  * [2] Favyen Bastani, Songtao He, Sofiane Abbar, Mohammad Alizadeh, Hari Balakrishnan, Sanjay Chawla, Sam Madden, and David DeWitt.  Roadtracer: Automatic extraction of road networks from aerial images.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4720–4728, 2018.
  * [3] Martin Büchner, Jannik Zürn, Ion-George Todoran, Abhinav Valada, and Wolfram Burgard.  Learning and aggregating lane graphs for urban automated driving.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13415–13424, 2023.
  * [4] 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.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11621–11631, 2020.
  * [5] Yuning Chai, Benjamin Sapp, Mayank Bansal, and Dragomir Anguelov.  Multipath: Multiple probabilistic anchor trajectory hypotheses for behavior prediction.  arXiv preprint arXiv:1910.05449, 2019.
  * [6] Dian Chen and Philipp Krähenbühl.  Learning from all vehicles.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 17222–17231, 2022.
  * [7] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  In Proceedings of the European conference on computer vision (ECCV), pages 801–818, 2018.
  * [8] Pascal Colling, Dennis Müller, and Matthias Rottmann.  Hd lane map generation based on trail map aggregation.  In 2022 IEEE Intelligent Vehicles Symposium (IV), pages 600–606. IEEE, 2022.
  * [9] Julie Dequaire, Peter Ondrúška, Dushyant Rao, Dominic Wang, and Ingmar Posner.  Deep tracking in the wild: End-to-end tracking using recurrent neural networks.  The International Journal of Robotics Research, 37(4-5):492–512, 2018.
  * [10] 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.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11525–11533, 2020.
  * [11] Thomas Gilles, Stefano Sabatini, Dzmitry Tsishkou, Bogdan Stanciulescu, and Fabien Moutarde.  Home: Heatmap output for future motion estimation.  In 2021 IEEE International Intelligent Transportation Systems Conference (ITSC), pages 500–507. IEEE, 2021.
  * [12] Thomas Gilles, Stefano Sabatini, Dzmitry Tsishkou, Bogdan Stanciulescu, and Fabien Moutarde.  Thomas: Trajectory heatmap output with learned multi-agent sampling.  arXiv preprint arXiv:2110.06607, 2021.
  * [13] Thomas Gilles, Stefano Sabatini, Dzmitry Tsishkou, Bogdan Stanciulescu, and Fabien Moutarde.  Gohome: Graph-oriented heatmap output for future motion estimation.  In 2022 International Conference on Robotics and Automation (ICRA), pages 9107–9114. IEEE, 2022.
  * [14] Songtao He and Hari Balakrishnan.  Lane-level street map extraction from aerial imagery.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 2080–2089, 2022.
  * [15] Namdar Homayounfar, Wei-Chiu Ma, Justin Liang, Xinyu Wu, Jack Fan, and Raquel Urtasun.  Dagmapper: Learning to map by discovering lane topology.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2911–2920, 2019.
  * [16] Robin Karlsson, Alexander Carballo, Francisco Lepe-Salazar, Keisuke Fujii, Kento Ohtani, and Kazuya Takeda.  Learning to predict navigational patterns from partial observations.  arXiv preprint arXiv:2304.13242, 2023.
  * [17] Peter Ondruska and Ingmar Posner.  Deep tracking: Seeing beyond seeing using recurrent neural networks.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
  * [18] Tim Salzmann, Boris Ivanovic, Punarjay Chakravarty, and Marco Pavone.  Trajectron++: Dynamically-feasible trajectory forecasting with heterogeneous data.  In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XVIII 16, pages 683–700. Springer, 2020.
  * [19] Yong-Qiang Tan, Shang-Hua Gao, Xuan-Yi Li, Ming-Ming Cheng, and Bo Ren.  Vecroad: Point-based iterative graph exploration for road graphs extraction.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8910–8918, 2020.
  * [20] OpenPCDet Development Team.  Openpcdet: An open-source toolbox for 3d object detection from point clouds.  https://github.com/open-mmlab/OpenPCDet, 2020.
  * [21] Lorenz Wellhausen, Alexey Dosovitskiy, René Ranftl, Krzysztof Walas, Cesar Cadena, and Marco Hutter.  Where should i walk? predicting terrain properties from images via self-supervised learning.  IEEE Robotics and Automation Letters, 4(2):1509–1516, 2019.
  * [22] Benjamin Wilson, William Qi, Tanmay Agarwal, John Lambert, Jagjeet Singh, Siddhesh Khandelwal, Bowen Pan, Ratnesh Kumar, Andrew Hartnett, Jhony Kaesemodel Pontes, et al.  Argoverse 2: Next generation datasets for self-driving perception and forecasting.  arXiv preprint arXiv:2301.00493, 2023.
  * [23] Huazhe Xu, Yang Gao, Fisher Yu, and Trevor Darrell.  End-to-end learning of driving models from large-scale video datasets.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2174–2182, 2017.
  * [24] Tianwei Yin, Xingyi Zhou, and Philipp Krahenbuhl.  Center-based 3d object detection and tracking.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11784–11793, 2021.
  * [25] Jimuyang Zhang and Eshed Ohn-Bar.  Learning by watching.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12711–12721, 2021.
  * [26] Tongjie Y Zhang and Ching Y. Suen.  A fast parallel algorithm for thinning digital patterns.  Communications of the ACM, 27(3):236–239, 1984.
  * [27] Hang Zhao, Jiyang Gao, Tian Lan, Chen Sun, Ben Sapp, Balakrishnan Varadarajan, Yue Shen, Yi Shen, Yuning Chai, Cordelia Schmid, et al.  Tnt: Target-driven trajectory prediction.  In Conference on Robot Learning, pages 895–904. PMLR, 2021.
  * [28] Tianyang Zhao, Yifei Xu, Mathew Monfort, Wongun Choi, Chris Baker, Yibiao Zhao, Yizhou Wang, and Ying Nian Wu.  Multi-agent tensor fusion for contextual trajectory prediction.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12126–12134, 2019.
  * [29] Jannik Zürn, Wolfram Burgard, and Abhinav Valada.  Self-supervised visual terrain classification from unsupervised acoustic feature learning.  IEEE Transactions on Robotics, 37(2):466–481, 2020.
  * [30] Jannik Zürn, Johan Vertens, and Wolfram Burgard.  Lane graph estimation for scene understanding in urban driving.  IEEE Robotics and Automation Letters, 6(4):8615–8622, 2021.
  * [31] Jannik Zürn, Sebastian Weber, and Wolfram Burgard.  Trackletmapper: Ground surface segmentation and mapping from traffic participant trajectories.  In 6th Annual Conference on Robot Learning, 2022.