# Efficient In-Context Learning in Vision-Language Models for Egocentric
Videos

Keunwoo Peter Yu Zheyuan Zhang Fengyuan Hu Joyce Chai
University of Michigan
Ann Arbor, MI, USA
<EMAIL_ADDRESS>
###### Abstract

Recent advancements in text-only large language models (LLMs) have highlighted
the benefit of in-context learning for adapting to new tasks with a few
demonstrations. However, extending in-context learning to large vision-
language models (VLMs) using a huge amount of naturalistic vision-language
data has shown limited success, particularly for egocentric videos, due to
high data collection costs. We propose a novel training method
$\mathbb{E}$fficient $\mathbb{I}$n-context $\mathbb{L}$earning on
$\mathbb{E}$gocentric $\mathbb{V}$ideos ($\mathbb{EILEV}$), which elicits in-
context learning in VLMs for egocentric videos without requiring massive,
naturalistic egocentric video datasets. $\mathbb{EILEV}$ involves
architectural and training data adaptations to allow the model to process
contexts interleaved with video clips and narrations, sampling of in-context
examples with clusters of similar verbs and nouns, use of data with skewed
marginal distributions with a long tail of infrequent verbs and nouns, as well
as homonyms and synonyms. Our evaluations show that $\mathbb{EILEV}$-trained
models outperform larger VLMs trained on a huge amount of naturalistic data in
in-context learning. Furthermore, they can generalize to not only out-of-
distribution, but also novel, rare egocentric videos and texts via in-context
learning, demonstrating potential for applications requiring cost-effective
training, and rapid post-deployment adaptability. Our code and demo are
available at https://github.com/yukw777/EILEV.

Figure 1: $\mathbb{EILEV}$ elicits in-context learning capabilities in VLMs
for egocentric videos by allowing the model to handle data interleaved with
videos and texts, and training it on data with clusters of similar verbs and
nouns, a long tail distribution of infrequent items and both homonyms and
synonyms. The resulting model not only generates more accurate action
narrations than other VLMs with more parameters and training data, but also
generalizes to novel, rare actions via in-context learning.

##  1 Introduction

In recent years, in-context learning in text-only large language models (LLMs)
has garnered much attention in and outside of the AI research community as it
allows rapid adaptability to novel tasks with only a few demonstrations
without the expensive task-specific fine-tuning step. This emergent behavior
has been observed to improve with the model size, as well as training data
size and diversity [4]. Naturally, there have been many efforts to extend the
impressive in-context learning capabilities to vision-language settings by
following the same methodology of collecting a huge amount of naturalistic
vision-language data and training a large vision-language model (VLM) [13, 14,
25, 1, 2, 17]. While these models have shown some success in performing in-
context learning, their usage is limited to turn-based interactions such as
chatbots due to the limited nature of their training data, i.e., scraped web
pages with images and texts. It is not yet clear whether and how these models
can support robust in-context learning on egocentric videos, an important
medium for embodied AI and interactive task-guidance systems from egocentric
video.

One possible way to improve the performance of these large VLMs on egocentric
videos is to collect a large amount of naturalistic data with egocentric
videos and texts. However, collecting such data is an extremely costly
endeavor, because the egocentric viewpoint is not yet a primary way in which
people interact with the Internet as wearable virtual or augmented reality
headsets are not yet widespread. For example, Ego4D [12], despite being the
biggest egocentric video dataset at the time of writing, is not large enough
to give rise to in-context learning in VLMs. Simulations may help, but they
still require laborious and expensive creation or acquisition of realistic and
naturalistic assets. This challenge then begs the question, “can we still
elicit in-context learning capabilities in VLMs for egocentric videos only
using the limited data available today?”

Chan _et al_. [5] have shown that certain distributional properties of the
training data with (1) entities that tend to appear in clusters, (2) skewed
marginal distributions with a long tail of infrequent items, and (3) dynamic
meaning with homonyms and synonyms give rise to in-context learning
capabilities in text-only LLMs. However, it is not clear if their findings
hold true for VLMs for egocentric videos and texts. Motivated by these
findings, we propose a novel training method $\mathbb{E}$fficient
$\mathbb{I}$n-context $\mathbb{L}$earning on $\mathbb{E}$gocentric
$\mathbb{V}$ideos or $\mathbb{EILEV}$ that is designed to elicit in-context
learning capabilities in VLMs for egocentric videos and texts without a
massive, naturalistic egocentric video dataset. Figure 1 shows an overview of
$\mathbb{EILEV}$, which includes the following modifications: (1) We adapt the
model architecture and training data so that the model can handle data
interleaved with videos and texts, which allows context modeling, (2) We
sample in-context examples so that similar verbs and nouns appear in clusters,
which helps the model learn to extract relevant information from the context,
(3) We ensure that our training data have skewed marginal distributions with a
long tail of infrequent verbs and nouns, which encourages the model to rely on
the context for infrequent verbs and nouns, and (4) We ensure that our
training data have homonyms and synonyms, which encourages the model to rely
on the context to disambiguate.

The contributions of our work are as follows: (1) We propose a novel training
method that can elicit in-context learning capabilities in VLMs for egocentric
videos and texts without a massive, naturalistic egocentric video dataset, (2)
We demonstrate that VLMs trained via our novel training method can generalize
to not only out-of-distribution egocentric actions, but also novel and rare
ones via in-context learning, (3) We show that VLMs trained via our novel
training method outperform larger VLMs that have been trained on a huge amount
of naturalistic data via in-context learning, and (4) Our novel training
method opens doors to incorporating in-context-learning-capable VLMs into
applications with a high cost of training data collection, and rapid, post-
deployment adaptability requirements such as interactive task-guidance systems
from egocentric video.

##  2 Related Works

###  2.1 Egocentric Video Datasets

Egocentric video datasets have garnered much attention in the past decade
thanks to their potential application in interesting research areas such as
embodied AI and interactive task-guidance systems from egocentric video. Most
of the large egocentric video datasets contain unscripted activities [8, 9,
15, 31, 26, 11, 12], while others have collected (semi-)scripted activities
where camera wearers are asked to follow certain instructions [30, 20, 29].
Our focus is to train a VLM that can perform in-context learning over
egocentric videos and texts, and we take advantage of egocentric video
datasets that contain unscripted activities, namely Ego4D [12] and EPIC-
KITCHENS-100 [9], because they are the largest at the time of writing with
diverse sets of activities.

###  2.2 In-context Learning

In-context learning was first proposed by Brown _et al_. [4] in their paper
introducing GPT-3. It is a significant departure from the traditional learning
method based on stochastic gradient descent and does not involve any parameter
updates: the model just needs to be provided with a few examples of the task
as part of the context for text generation. The size of the model and training
data was thought to be key to training a model with in-context learning
capabilities.

More recently, there has been more research on the exact causes of in-context
learning. Min _et al_. [24] has proposed MetaICL, a meta-training framework to
elicit in-context learning capabilities in text-only language models. MetaICL
conditions each example with related in-context examples during training. Chan
_et al_. [5] have investigated the distributional properties of training data
for in-context learning. Their findings have shown that there are certain
properties that encourage in-context learning in language models, and massive
textual data from the web used to train large language models naturally have
those properties.

Our work takes the findings of the related works in in-context learning and
extends them to VLMs, specifically for egocentric videos.

###  2.3 Generative Vision-Language Models

With the recent success of text-only LLMs, there have been various efforts to
replicate their success in multi-modal settings, especially vision and
language. A couple of different types of approaches in training generative
VLMs have been proposed. The first is to train one from scratch using large
language-only and vision-language datasets [13, 14, 25]. This approach allows
the most controllability and flexibility, but requires a massive amount of
compute and data. In order to address these challenges, a number of approaches
have been proposed to connect a pretrained large language model and a
pretrained vision model to create a single VLM [1, 17, 37, 22, 18, 19, 6].

We utilize a model that follows the second approach in our evaluations.
However, our main contribution is a novel training method to elicit in-context
learning capabilities in VLMs on egocentric videos, which can be applied to
any generative VLM.

##  3 Method

We propose $\mathbb{EILEV}$, a novel training method that can be used to
elicit in-context learning capabilities in VLMs for egocentric videos without
a massive, naturalistic egocentric video dataset. This section introduces the
details of $\mathbb{EILEV}$, specifically the modifications made to the model
architecture and training data.

###  3.1 Context Modeling

By definition, a model capable of in-context learning must be able to model
the context. For a VLM, this means that it needs to be able to infer
relationships between video clips and texts in the context and extract
relevant information about the query from them. Prior works have noted that
ensuring that training data are interleaved with images, video clips and texts
and the VLM can properly process them is key to achieving this [1, 13, 19]. In
our work, we follow the approach proposed by Hao _et al_. [13], and augment
BLIP-2 [19], whose original implementation is not able to handle data
interleaved with video clips and texts, to use its frozen language model as
the universal interface for video clips and texts. Furthermore, we construct
each context-query instance to the model to be interleaved with video clips
and texts.

Figure 2: Architectural modifications to allow context modeling. We first
encode each frame of each video clip into a sequence of vision tokens using
the frozen image encoder of BLIP-2. We then compress the sequence of vision
tokens into a fixed-length sequence using the Q-Former. The compressed tokens
are then interleaved with text tokens following the order of the original
context-query instance. Finally, the interleaved tokens are passed to the
frozen language model of BLIP-2, which generates new text tokens.

Figure 2 shows an overview of our modifications to BLIP-2. Given an
interleaved context-query instance, we first encode all the video clips using
BLIP-2’s frozen Vision Transformer (ViT)-based [10] vision encoder.
Specifically, we independently encode sampled frames to produce a sequence of
vision tokens for each video clip. The sequence of vision tokens is then
compressed by the Q-Former into a fixed-length sequence. The compressed
sequence is further projected to the word embedding space of the frozen
language model of BLIP-2 by a linear layer. It is then interleaved with the
text tokens according to the order in which video clips and texts appear in
the context-query instance to form the input to the frozen language model.

###  3.2 Training Data for In-context Learning

Since Brown _et al_. [4] have discovered in-context learning in text-only
LLMs, there has been much research into the cause for in-context learning. In
particular, Chan _et al_. [5] have found that the following characteristics of
the training data are important in eliciting in-context learning capabilities
in Transformer-based LLMs:

  1. 1.

Entities that tend to appear in clusters (bursty distributions).

  2. 2.

Skewed marginal distributions with a long tail of infrequent items.

  3. 3.

Dynamic meaning where a single entity can have multiple possible
interpretations (homonyms), and multiple entities can map to the same
interpretation (synonyms).

They have further noted that naturalistic language data used to train LLMs
have these characteristics, and this is the key contributor to text-only LLMs’
in-context learning capabilities. Based on their findings, we reframe Ego4D
[12], currently the largest egocentric video dataset, to construct a training
dataset with these characteristics. Thankfully, video clips and action
narrations in Ego4D already have skewed marginal distributions and dynamic
meaning as egocentric videos submitted to Ego4D contain common daily
activities more frequently than rare activities, and action narrations are in
natural language with homonyms and synonyms.

Figure 3: An example of a context-query instance in the training dataset
generated from Ego4D video clips and action narrations. We interleave video
clips and action narrations to encourage the model to learn the relationships
between them, and make an inference based on the context. Furthermore, we
sample video clips and action narrations with the same verb class as the query
for half of the context, and we sample those with the same noun class for the
other half. This is to ensure that none of the video clips and action
narrations in the context share both the verb and noun class with the query
simultaneously. This helps the training data have the bursty data
characteristic where similar entities tend to appear in clusters. We generate
about 115K context-query instances from Ego4D.

In order to satisfy the remaining characteristic of bursty distributions, we
take advantage of the additional annotations from Ego4D where each video clip
is annotated with a verb class and a noun class based on the main action.
Specifically, we sample video clips and action narrations that share the same
verb class as the query for half of the context, and we sample those with the
same noun class for the other half. In cases where there are not enough video
clips and action narrations with matching verb classes or noun classes to form
the full context, we randomly sample additional video clips and narrations
from the rest of the dataset. We further ensure that none of the sampled video
clips and action narrations match both the verb class and noun class of the
query simultaneously. This ensures that the context only provides partial
information regarding the query, and encourages the model to extract useful
information from the context to make inferences about the query. This sampling
strategy ensures that each context-query instance has bursty distributions
with clusters of similar actions and objects. We finally turn the action
narrations into question-answer pairs where the answers are the action
narrations. Figure 3 shows an example of a context-query instance constructed
via the strategy described in this section. We are able to generate about 115K
context-query instances from Ego4D.

The training objective is to maximize the likelihood of the ground-truth
answer, i.e., the action narration, conditioned on the context and the video
clip of the query. For prefix language models, the interleaved tokens for the
context as well as the tokens corresponding to the question of the query are
used as the prefix, while those corresponding to the answer for the query are
used as the generated sequence to calculate losses. For causal language
models, the tokens for both the context and the query are given to the model,
and losses are calculated over tokens that correspond to the answer of the
query. This is to compensate for the relatively synthetic nature of our
modified dataset, as well as the imbalance between question tokens and action
narration tokens.

##  4 Evaluation

In this section, we describe the various evaluations we have performed on
models trained using $\mathbb{EILEV}$ in detail. We first describe the details
of the models we use for our evaluations and the metrics we use to measure
their performances. We then describe the evaluations and report the results.

###  4.1 Experimental Setups

##### Models

Model | MMI Dataset Size | Train. Params.
---|---|---
$\mathbb{EILEV}$ BLIP-2 OPT-2.7B & Flan-T5-xl |  115K context-query instances |
188M
BLIP-2 OPT-2.7B & Flan-T5-xl [19] |  |
0 | 188M
Kosmos-2 [25] |  71M image-text webpages [14] | 1.6B
|  101.2M image-text webpages [38] & 2.8M context-query instances [16] | 1.3B
Otter [17] |
Table 1: Models used for evaluations and their multi-modal interleaved (MMI)
dataset sizes, as well as their trainable parameters. The
$\mathbb{EILEV}$-trained BLIP-2 models have far fewer trainable parameters and
are trained on far less MMI data than Kosmos-2 and Otter.

Table 1 shows all the models we use for our evaluations with the numbers of
their trainable parameters and multi-modal interleaved (MMI) dataset sizes. We
refer to data interleaved with images, videos and texts as MMI data. Note that
Kosmos-2 has been trained on other types of data than MMI such as text-only
data and image-text pair data [14]. Otter’s MMI dataset has partially been
generated from Ego4D [16]. BLIP-2 has been trained only on image-text pair
data [19]. The $\mathbb{EILEV}$-trained BLIP-2 models have far fewer trainable
parameters and are trained on far less MMI data than Kosmos-2 and Otter.

We train two variants of BLIP-2 using $\mathbb{EILEV}$: BLIP-2 with 2.7
billion parameter OPT [35] as its frozen language model (BLIP-2 OPT-2.7B), and
BLIP-2 with XL-size Flan-T5 [34] as its frozen language model (BLIP-2
Flan-T5-xl). Following the fine-tuning procedure of Li _et al_. [19], we
freeze the vision encoder and language model of the BLIP-2 models when
training them using $\mathbb{EILEV}$. For both variants, the total training
batch size is 128 and the optimizer is AdamW [23] with the initial learning
rate of $1\times 10^{-5}$, weight decay of 0.05 and a linear scheduler. We
train for 5 epochs on 8 NVIDIA A40 GPUs using distributed data parallel. We
evaluate every 200 steps and select the model with the lowest loss. The total
training time for both variants is about a day and a half.

Training context-query instances are formed by sampling both the context and
query from the train split. The context contains 16 video clip and action
narration pairs for training. Each video clip is created by taking the four
seconds before and after its action narration timestamp. We then sample 8
frames uniformly from each of the 8-second video clips. For Kosmos-2 and
Otter, we treat the sampled frames as separate images.

For all evaluations, the models are provided with the same context-query
instances. We vary the number of video clip and action narration pairs in the
context for evaluation at 0, 1, 2, 4, 8, 12 and 16 shot. The only exception is
Kosmos-2 for which we only perform evaluations up to 2 shot. This is because
Kosmos-2 runs out of its context window beyond 2 shot as it does not compress
the tokens for video clips. We apply our architectural modifications (Section
4.4) to the vanilla BLIP-2 models as they cannot be used for our evaluations
otherwise, because they cannot process context-query instances interleaved
with videos and texts.

##### Metrics

One major difficulty in evaluating generative models for the action narration
generation task is that there is no single correct way to describe the action
in the video clip. For example, given the ground-truth action narration “The
camera wearer cuts an onion,” a generated action narration “The camera wearer
slices an onion,” while not strictly the same as the ground truth, is not
incorrect either. In an ideal world, we would rely on human annotators to rate
how close a generated action narration is to the ground truth, but the cost to
do so would be prohibitive. In order to address this challenge, a number of
semantic-similarity-based metrics [36, 28] that correlate closely with human
judgment have been proposed, and we take advantage of them in our evaluations.
Specifically, we report the in-context learning performances at different
numbers of shots in terms of semantic-similarity-based scores produced by
Siamese Sentence-BERT Bi-Encoder (STS-BE) [28], which is a cosine-similarity
measure that ranges from -1 to 1. We also report the lexical-based metric
ROUGE-L [21] for completeness.

###  4.2 In-Context Learning Capabilities

We first evaluate if $\mathbb{EILEV}$ can indeed elicit in-context learning
capabilities in BLIP-2 models to generate action narrations for unseen video
clips. Specifically, we train the two BLIP-2 variants using context-query
instances formed from Ego4D, then evaluate them on a held-out test set also
from Ego4D. Evaluation context-query instances are formed by sampling the
context from the train split and the query from the held-out test set.

Figure 4: In-context learning capability evaluation results. We report the
semantic-similarity-based STS-BE scores and lexical-based ROUGE-L scores for
different numbers of shots sampled from Ego4D. Solid lines are the
$\mathbb{EILEV}$-trained models and dotted lines are the baselines. The
$\mathbb{EILEV}$-trained models clearly show superior in-context-learning
capabilities to the baselines for unseen video clips.

Figure 4 reports the evaluation results. The $\mathbb{EILEV}$-trained BLIP-2
models clearly show superior in-context-learning capabilities, outperforming
all the baselines from 1 to 16 shot. This is a clear indication that
$\mathbb{EILEV}$ has successfully elicited in-context-learning capabilities in
them. Surprisingly, Kosmos-2 and Otter perform worse as they are given more
in-context examples. It is true that they have not been fine-tuned for this
particular task, but they are much larger models trained on an enormous amount
of naturalistic data (See Table 1), so it is not unreasonable to expect them
to perform better with more in-context examples, even outperforming the
$\mathbb{EILEV}$-trained BLIP-2 models. This observation underscores that
training a smaller VLM using a more focused approach like $\mathbb{EILEV}$ can
be more beneficial for certain use-cases than training a large, generalist VLM
on a huge naturalistic dataset.

The $\mathbb{EILEV}$-trained BLIP-2 models outperform the vanilla BLIP-2
models and are on par with Kosmos-2 and Otter at 0 shot, where they only have
knowledge encoded in their parameters at their disposal (in-weights learning).
This shows that the $\mathbb{EILEV}$-trained BLIP-2 models have encoded some
knowledge about Ego4D actions in their parameters.

Interestingly, despite the authors’ claim that BLIP-2 models are not capable
of in-context learning [19], BLIP-2 OPT-2.7B and BLIP-2 Flan-T5-xl seem to
benefit from in-context examples to a certain degree, with a sizable jump in
performance from 0 to 1 shot. We investigate this phenomenon in detail in
Section 4.4.

###  4.3 Generalization Capabilities

In this section, we test various generalization capabilities of the
$\mathbb{EILEV}$-trained models via in-context learning. Specifically, we
evaluate their generalizability to out-of-distribution actions by using video
clips and action narrations from a different egocentric video dataset EPIC-
KITCHENS-100. Furthermore, we evaluate their generalizability to novel, rare
actions by dividing the actions from Ego4D into common and rare actions.

####  4.3.1 Out-of-Distribution Actions

In this evaluation, we test if BLIP-2 models trained exclusively on Ego4D
using $\mathbb{EILEV}$ can generalize to out-of-distribution actions from the
validation split of an entirely different egocentric video dataset EPIC-
KITCHENS-100 via in-context learning. Evaluation context-query instances are
formed by sampling both the context and the query from the validation set of
EPIC-KITCHENS-100. Unlike Ego4D, the action narrations from EPIC-KITCHENS-100
are not full sentences, but simple verb-noun pairs. Therefore, we use an LLM
(2.7 billion parameter Llama-2-Chat [32]) to turn the simple verb-noun pairs
into full sentences with “the camera wearer” as the subject.

Figure 5: Out-of-distribution action evaluation results on EPIC-KITCHENS-100.
We report the semantic-similarity-based STS-BE scores and lexical-based
ROUGE-L scores for different numbers of shots sampled from EPIC-KITCHENS-100.
The $\mathbb{EILEV}$-trained models are trained exclusively on Ego4D. Solid
lines are the $\mathbb{EILEV}$-trained models and dotted lines are the
baselines. It is evident that $\mathbb{EILEV}$-trained models can generalize
to out-of-distribution actions as their performances improve with more shots.

Figure 5 reports the evaluation results. The performances of the
$\mathbb{EILEV}$-trained BLIP-2 models improve with more in-context examples,
indicating that the $\mathbb{EILEV}$-trained models can generalize to out-of-
distribution actions via in-context learning. Kosmos-2 and Otter again perform
worse with more in-context examples, which again lends support to the claim
that a more focused approach like $\mathbb{EILEV}$ can be more beneficial even
for generalizability to out-of-distribution actions than collecting a huge
naturalistic egocentric video dataset and training a large, generalist VLM.

The 0-shot performances of the $\mathbb{EILEV}$-trained BLIP-2 models are
lower than observed in Section 4.2, which is expected as actions from EPIC-
KITCHENS-100 are not part of their training data. As a result, they are
outperformed at 0-shot by Kosmos-2 and Otter, larger VLMs with more knowledge
in their weights from a huge amount of naturalistic training data (See Table
1).

The vanilla BLIP-2 models show a similar trend as in 4.2 where their
performance levels see a sudden jump from 0 to 1 shot before quickly tapering
off in subsequent shots. We investigate their apparent in-context learning
capabilities in Section 4.4.

####  4.3.2 Novel, Rare Actions

Figure 6: Action frequency plot. We calculate the frequencies of verb-noun-
class-pairs in Ego4D. We then designate the most frequent 80% as common
actions and the remaining 20% as rare actions. The x-axis shows samples of
common and rare actions.

In this evaluation, we seek to validate that $\mathbb{EILEV}$ can be used in a
practical situation where a model is trained on data only with “common”
actions, but can still generalize to novel, “rare” actions via in-context
learning once deployed. To that end, we take advantage of Ego4D’s additional
annotations where each narrated action is annotated with a verb class and a
noun class (discussed in Section 3.2). Specifically, we calculate the
frequencies of these verb-noun-class pairs, and designate the most frequent
80% as common actions, and the remaining 20% as rare actions (Figure 6).
Training context-query instances are formed by sampling both the context and
the query from the common actions, while evaluation context-query instances
are formed by sampling both from the rare actions. It is important to note
that while none of the rare actions are part of the training context-query
instances, they still contain actions that share either the verb or noun
classes with the rare actions. For example, if the training context-query
instances do not include a rare action (“put”, “bench”), they may still
include (“put”, “key”) or (“sit”, “bench”).

Figure 7: Novel, rare action evaluation results. We report the semantic-
similarity-based STS-BE scores and lexical-based ROUGE-L scores for different
numbers of shots sampled from the rare actions. The $\mathbb{EILEV}$-trained
models are trained only on the common actions and do not see the rare actions
during training. Solid lines are the $\mathbb{EILEV}$-trained models and
dotted lines are the baselines. It is evident that the
$\mathbb{EILEV}$-trained models can generalize to novel, rare actions as their
performances improve with more shots.

Figure 7 shows the evaluation results. The performances of the
$\mathbb{EILEV}$-trained BLIP-2 models improve with more in-context examples,
demonstrating that the $\mathbb{EILEV}$-trained models can generalize to
novel, rare actions unseen during training via in-context learning. Similar to
Section 4.3.1, Kosmos-2 and Otter outperform the $\mathbb{EILEV}$-trained
BLIP-2 models at 0-shot, but they again fail to utilize in-context examples.
The vanilla BLIP-2 models show a similar trend as in 4.2, which is
investigated in detail in Section 4.4.

####  4.3.3 Source of Generalization to Novel, Rare Actions

In this evaluation, we aim to understand what drives the generalization of the
$\mathbb{EILEV}$-trained models to novel, rare actions: in-context learning or
in-weights learning. To that end, we use the frequency of each verb/noun class
in the common action training data as the proxy for the knowledge about the
verb/noun class encoded into the weights of the model (in-weights learning),
and the difference in model performance between 16-shot and 0-shot settings
for a particular rare action as the proxy for in-context learning performance.
If the model relies on in-weights learning for a particular novel, rare
action, the difference in performance for that action between 16-shot and
0-shot settings would be correlated to the frequency of the corresponding
verb/noun class in the training data. This outcome is not preferred, as we
want the model to rely on in-context learning for generating accurate
narrations of novel, rare actions unseen during training.

Figure 8: Scatter plots with trend lines and $R^{2}$ values between the log
verb/noun class frequency in the training data with common actions and the
difference in STS-BE ($\Delta$ STS-BE) for the corresponding rare action
between 16-shot and 0-shot settings for the $\mathbb{EILEV}$-trained models.
There is a minimal linear correlation between two measures, indicating that
the source of the generalizability of the $\mathbb{EILEV}$-trained models to
novel, rare actions is in-context learning.

Figure 8 shows the scatter plots between the log verb/noun class frequency in
the training data and the difference in STS-BE for the corresponding rare
action between 16-shot and 0-shot settings for the $\mathbb{EILEV}$-trained
models. For example, given a rare action (“put”, “bench”), a point on the
scatter plot may refer to the log frequency of “put” in the common action
training data in the x-axis and the difference in the STS-BE performance of
$\mathbb{EILEV}$ BLIP-2 OPT-2.7B on (“put”, “bench”) between 16-shot and
0-shot. As the scatter plots and their corresponding $R^{2}$ values show,
there is a minimal linear correlation between the log verb/noun class
frequency in the training data and the difference in STS-BE for the
corresponding action from in-context learning. This suggests that the
$\mathbb{EILEV}$-trained models synthesize accurate narrations for novel, rare
actions via in-context learning rather than in-weights learning, as the linear
model does not significantly account for the variance in the observed data.

###  4.4 Context Modeling and In-Context Learning

In this evaluation, we seek to investigate if the $\mathbb{EILEV}$-trained
BLIP-2 models perform correct context modeling by incorporating the
relationships between video clips and narrations. To that end, we evaluate the
BLIP-2 models trained on Ego4D using $\mathbb{EILEV}$ (Section 4.2) and the
vanilla BLIP-2 models on shuffled in-context examples where video clips no
longer match the action narrations. We then compare the performances from
shuffled in-context examples (the treatment group) to the results from un-
shuffled in-context examples (Section 4.2) as the control group. If the
performances remain unchanged, it implies that the model does not consider the
relationships between in-context video clips and action narrations. On the
other hand, if the performance levels decrease, it implies that the model does
take the relationships between video clips and action narrations into account,
and the mismatch adversely affects its performance. We do not report the
results at 0 and 1-shot since shuffling of the in-context video clips would
not have any impact at those settings.

Figure 9: Percentage difference plots between the treatment group with
shuffled in-context video clips and the control group. A negative value below
the dotted zero line means the STS-BE performance of the treatment group is
worse than the control group. The percentage differences are small for the
vanilla BLIP-2 models, indicating they do not consider the detailed
relationships between video clips and action narrations. The percentage
differences for STS-BE are negative for the $\mathbb{EILEV}$-trained BLIP-2
models, indicating that they extract semantic details from the relationships
between video clips and narrations.

Figure 9 shows the percentage differences in STS-BE from 16-shot to 0-shot
between the treatment group and the control group for the vanilla BLIP-2
models and the $\mathbb{EILEV}$-trained BLIP-2 models. For the vanilla BLIP-2
models, the percentage differences are small across all shots. This indicates
that they rely mostly on the context as a whole rather than the semantic
details from the relationships between video clips and action narrations when
performing in-context learning. We hypothesize that our proposed architectural
modifications allow the vanilla BLIP-2 models to tap into the text-only in-
context learning capabilities of their frozen language models, which lack the
ability to extract semantic details from the relationships between video clips
and action narrations. This hypothesis is supported by their subpar in-context
learning capabilities from our previous evaluations, which speaks to the
importance of our modifications to the training data from Section 3.2. On the
other hand, there is a clear drop in performance for the
$\mathbb{EILEV}$-trained BLIP-2 models in terms of the semantic-similarity-
based metric STS-BE. This indicates that the $\mathbb{EILEV}$-trained BLIP-2
models extract detailed semantic information from the correspondence between
in-context video clips and action narrations.

##  5 Conclusion

In this work, we propose a novel training method $\mathbb{E}$fficient
$\mathbb{I}$n-context $\mathbb{L}$earning on $\mathbb{E}$gocentric
$\mathbb{V}$ideos ($\mathbb{EILEV}$) that elicits in-context learning
capabilities in VLMs for egocentric videos without a huge amount of
naturalistic data. We adapt the model architecture and training data so that
the VLM can learn to model the context interleaved with video clips and action
narrations. Furthermore, we construct a training dataset with specific
characteristics by sampling in-context examples with clusters of similar verbs
and nouns and ensuring that data have skewed marginal distributions with a
long tail of infrequent verbs and nouns, as well as homonyms and synonyms.
Through extensive evaluations, we demonstrate that $\mathbb{EILEV}$-trained
models do indeed possess in-context learning capabilities despite not having
been trained on a huge amount of naturalistic data. We further show that they
can generalize to not only out-of-distribution videos and texts, but also
novel and rare actions via in-context learning, while outperforming larger
VLMs that have been trained on a huge amount of naturalistic data.

An $\mathbb{EILEV}$-trained VLM with in-context learning capabilities over
egocentric videos has a wide range of possible applications. One such
application is interactive task-guidance systems from egocentric video where
training data are hard to collect, and their rapid, post-deployment
adaptability requirements pose a serious challenge [3, 27, 7, 33].
$\mathbb{EILEV}$ can be used to train a small VLM with in-context learning
capabilities without a large amount of training data for an interactive task
guidance system. This VLM could offer the potential for rapid, post-deployment
adaptability to the task guidance system through in-context learning.

##### Acknowledgments

We thank Shane Storks for his valuable insight and comments. This work has
been supported by the Defense Advanced Research Projects Agency (DARPA) under
the PTG Program, Contract No. HR00112220003. The views expressed are those of
the authors and do not necessarily reflect the views of DARPA.

## References

  * Alayrac et al. [2022] Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katherine Millican, Malcolm Reynolds, Roman Ring, Eliza Rutherford, Serkan Cabi, Tengda Han, Zhitao Gong, Sina Samangooei, Marianne Monteiro, Jacob L Menick, Sebastian Borgeaud, Andy Brock, Aida Nematzadeh, Sahand Sharifzadeh, Mikoł aj Bińkowski, Ricardo Barreira, Oriol Vinyals, Andrew Zisserman, and Karén Simonyan.  Flamingo: a visual language model for few-shot learning.  In _Advances in Neural Information Processing Systems_ , pages 23716–23736. Curran Associates, Inc., 2022.
  * Awadalla et al. [2023] Anas Awadalla, Irena Gao, Josh Gardner, Jack Hessel, Yusuf Hanafy, Wanrong Zhu, Kalyani Marathe, Yonatan Bitton, Samir Gadre, Shiori Sagawa, et al.  Openflamingo: An open-source framework for training large autoregressive vision-language models.  _arXiv preprint arXiv:2308.01390_ , 2023.
  * Bao et al. [2023] Yuwei Bao, Keunwoo Peter Yu, Yichi Zhang, Shane Storks, Itamar Bar-Yossef, Alexander De La Iglesia, Megan Su, Xiao Lin Zheng, and Joyce Chai.  Can foundation models watch, talk and guide you step by step to make a cake?  _arXiv preprint arXiv:2311.00738_ , 2023.
  * Brown et al. [2020] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Chan et al. [2022] Stephanie Chan, Adam Santoro, Andrew Lampinen, Jane Wang, Aaditya Singh, Pierre Richemond, James McClelland, and Felix Hill.  Data distributional properties drive emergent in-context learning in transformers.  _Advances in Neural Information Processing Systems_ , 35:18878–18891, 2022.
  * Dai et al. [2023] Wenliang Dai, Junnan Li, Dongxu Li, Anthony Meng Huat Tiong, Junqi Zhao, Weisheng Wang, Boyang Li, Pascale Fung, and Steven Hoi.  Instructblip: Towards general-purpose vision-language models with instruction tuning, 2023.
  * Damen et al. [2016] Dima Damen, Teesid Leelasawassuk, and Walterio Mayol-Cuevas.  You-do, i-learn: Egocentric unsupervised discovery of objects and their modes of interaction towards video-based guidance.  _Computer Vision and Image Understanding_ , 149:98–112, 2016.
  * Damen et al. [2018] Dima Damen, Hazel Doughty, Giovanni Maria Farinella, Sanja Fidler, Antonino Furnari, Evangelos Kazakos, Davide Moltisanti, Jonathan Munro, Toby Perrett, Will Price, et al.  Scaling egocentric vision: The epic-kitchens dataset.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 720–736, 2018.
  * Damen et al. [2022] Dima Damen, Hazel Doughty, Giovanni Maria Farinella, Antonino Furnari, Jian Ma, Evangelos Kazakos, Davide Moltisanti, Jonathan Munro, Toby Perrett, Will Price, and Michael Wray.  Rescaling egocentric vision: Collection, pipeline and challenges for epic-kitchens-100.  _International Journal of Computer Vision (IJCV)_ , 130:33–55, 2022.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Fathi et al. [2012] Alircza Fathi, Jessica K Hodgins, and James M Rehg.  Social interactions: A first-person perspective.  In _2012 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 1226–1233. IEEE, 2012.
  * Grauman et al. [2022] Kristen Grauman, Andrew Westbury, Eugene Byrne, Zachary Chavis, Antonino Furnari, Rohit Girdhar, Jackson Hamburger, Hao Jiang, Miao Liu, Xingyu Liu, Miguel Martin, Tushar Nagarajan, Ilija Radosavovic, Santhosh Kumar Ramakrishnan, Fiona Ryan, Jayant Sharma, Michael Wray, Mengmeng Xu, Eric Zhongcong Xu, Chen Zhao, Siddhant Bansal, Dhruv Batra, Vincent Cartillier, Sean Crane, Tien Do, Morrie Doulaty, Akshay Erapalli, Christoph Feichtenhofer, Adriano Fragomeni, Qichen Fu, Christian Fuegen, Abrham Gebreselasie, Cristina Gonzalez, James Hillis, Xuhua Huang, Yifei Huang, Wenqi Jia, Weslie Khoo, Jachym Kolar, Satwik Kottur, Anurag Kumar, Federico Landini, Chao Li, Yanghao Li, Zhenqiang Li, Karttikeya Mangalam, Raghava Modhugu, Jonathan Munro, Tullie Murrell, Takumi Nishiyasu, Will Price, Paola Ruiz Puentes, Merey Ramazanova, Leda Sari, Kiran Somasundaram, Audrey Southerland, Yusuke Sugano, Ruijie Tao, Minh Vo, Yuchen Wang, Xindi Wu, Takuma Yagi, Yunyi Zhu, Pablo Arbelaez, David Crandall, Dima Damen, Giovanni Maria Farinella, Bernard Ghanem, Vamsi Krishna Ithapu, C. V. Jawahar, Hanbyul Joo, Kris Kitani, Haizhou Li, Richard Newcombe, Aude Oliva, Hyun Soo Park, James M. Rehg, Yoichi Sato, Jianbo Shi, Mike Zheng Shou, Antonio Torralba, Lorenzo Torresani, Mingfei Yan, and Jitendra Malik.  Ego4d: Around the World in 3,000 Hours of Egocentric Video.  In _IEEE/CVF Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Hao et al. [2022] Yaru Hao, Haoyu Song, Li Dong, Shaohan Huang, Zewen Chi, Wenhui Wang, Shuming Ma, and Furu Wei.  Language models are general-purpose interfaces.  _arXiv preprint arXiv:2206.06336_ , 2022.
  * Huang et al. [2023] Shaohan Huang, Li Dong, Wenhui Wang, Yaru Hao, Saksham Singhal, Shuming Ma, Tengchao Lv, Lei Cui, Owais Khan Mohammed, Qiang Liu, et al.  Language is not all you need: Aligning perception with language models.  _arXiv preprint arXiv:2302.14045_ , 2023.
  * Lee et al. [2012] Yong Jae Lee, Joydeep Ghosh, and Kristen Grauman.  Discovering important people and objects for egocentric video summarization.  In _2012 IEEE conference on computer vision and pattern recognition_ , pages 1346–1353. IEEE, 2012.
  * Li et al. [2023a] Bo Li, Yuanhan Zhang, Liangyu Chen, Jinghao Wang, Fanyi Pu, Jingkang Yang, Chunyuan Li, and Ziwei Liu.  Mimic-it: Multi-modal in-context instruction tuning.  _arXiv preprint arXiv:2306.05425_ , 2023a.
  * Li et al. [2023b] Bo Li, Yuanhan Zhang, Liangyu Chen, Jinghao Wang, Jingkang Yang, and Ziwei Liu.  Otter: A multi-modal model with in-context instruction tuning.  _arXiv preprint arXiv:2305.03726_ , 2023b.
  * Li et al. [2022] Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  In _International Conference on Machine Learning_ , pages 12888–12900. PMLR, 2022.
  * Li et al. [2023c] Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi.  Blip-2: Bootstrapping language-image pre-training with frozen image encoders and large language models.  _arXiv preprint arXiv:2301.12597_ , 2023c.
  * Li et al. [2018] Yin Li, Miao Liu, and James M Rehg.  In the eye of beholder: Joint learning of gaze and actions in first person video.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 619–635, 2018.
  * Lin [2004] Chin-Yew Lin.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , pages 74–81, 2004.
  * Liu et al. [2023] Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee.  Visual instruction tuning.  _arXiv preprint arXiv:2304.08485_ , 2023.
  * Loshchilov and Hutter [2017] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_ , 2017.
  * Min et al. [2021] Sewon Min, Mike Lewis, Luke Zettlemoyer, and Hannaneh Hajishirzi.  Metaicl: Learning to learn in context.  _arXiv preprint arXiv:2110.15943_ , 2021.
  * Peng et al. [2023] Zhiliang Peng, Wenhui Wang, Li Dong, Yaru Hao, Shaohan Huang, Shuming Ma, and Furu Wei.  Kosmos-2: Grounding multimodal large language models to the world.  _arXiv preprint arXiv:2306.14824_ , 2023.
  * Pirsiavash and Ramanan [2012] Hamed Pirsiavash and Deva Ramanan.  Detecting activities of daily living in first-person camera views.  In _2012 IEEE conference on computer vision and pattern recognition_ , pages 2847–2854. IEEE, 2012.
  * Qian et al. [2017] Kun Qian, Wei Zhao, Zhewen Ma, Jiale Ma, Xudong Ma, and Hai Yu.  Wearable-assisted localization and inspection guidance system using egocentric stereo cameras.  _IEEE Sensors Journal_ , 18(2):809–821, 2017.
  * Reimers and Gurevych [2019] Nils Reimers and Iryna Gurevych.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, 2019.
  * Sener et al. [2022] Fadime Sener, Dibyadip Chatterjee, Daniel Shelepov, Kun He, Dipika Singhania, Robert Wang, and Angela Yao.  Assembly101: A large-scale multi-view video dataset for understanding procedural activities.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 21096–21106, 2022.
  * Sigurdsson et al. [2018] Gunnar A Sigurdsson, Abhinav Gupta, Cordelia Schmid, Ali Farhadi, and Karteek Alahari.  Charades-ego: A large-scale dataset of paired third and first person videos.  _arXiv preprint arXiv:1804.09626_ , 2018.
  * Su and Grauman [2016] Yu-Chuan Su and Kristen Grauman.  Detecting engagement in egocentric video.  In _Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part V 14_ , pages 454–471. Springer, 2016.
  * Touvron et al. [2023] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023.
  * Wang et al. [2023] Xin Wang, Taein Kwon, Mahdi Rad, Bowen Pan, Ishani Chakraborty, Sean Andrist, Dan Bohus, Ashley Feniello, Bugra Tekin, Felipe Vieira Frujeri, et al.  Holoassist: an egocentric human interaction dataset for interactive ai assistants in the real world.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 20270–20281, 2023.
  * Wei et al. [2021] Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le.  Finetuned language models are zero-shot learners.  _arXiv preprint arXiv:2109.01652_ , 2021.
  * Zhang et al. [2022] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al.  Opt: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_ , 2022.
  * Zhang et al. [2019] Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q Weinberger, and Yoav Artzi.  Bertscore: Evaluating text generation with bert.  _arXiv preprint arXiv:1904.09675_ , 2019.
  * Zhao et al. [2023] Yue Zhao, Ishan Misra, Philipp Krähenbühl, and Rohit Girdhar.  Learning video representations from large language models.  In _CVPR_ , 2023.
  * Zhu et al. [2023] Wanrong Zhu, Jack Hessel, Anas Awadalla, Samir Yitzhak Gadre, Jesse Dodge, Alex Fang, Youngjae Yu, Ludwig Schmidt, William Yang Wang, and Yejin Choi.  Multimodal c4: An open, billion-scale corpus of images interleaved with text.  _arXiv preprint arXiv:2304.06939_ , 2023.


# Development of a Tracklet Extraction Engine

Ryou Ohsawa∗1

###### Abstract

An efficient algorithm is required to extract moving objects (asteroids,
satellites, and space debris) from enormous data with advances in
observational instruments. We have developed an algorithm, tracee, to swiftly
detect points aligned as a line segment from a three-dimensional space. The
algorithm consists of two steps; First, construct a $k$-nearest neighbor graph
of given points, and then extract colinear line segments by grouping. The
proposed algorithm is robust against distractors and works properly even when
line segments are crossed. While the algorithm is originally developed for
moving object detection, it can be used for other purposes.

## 1\. Introduction

Solar system small bodies are relatively small objects orbiting around the
Sun, such as asteroids, comets, and meteoroids. More than one million objects
have been discovered as of August 2020111The number is adopted from the Minor
Planet Center ().. The objects whose perihelion distances are smaller than 1.3
au are called Near-Earth Objects (NEOs). Their population, orbits, sizes, and
compositions provide vital information to understanding the solar system’s
evolution (e.g., Granvik et al. 2018, Bottke et al. 2002). Besides, some of
them are potentially hazardous to the Earth. Thus, detecting NEOs is crucial
as well in the context of planetary defense. However, many NEOs, especially
smaller ones, remain undiscovered (e.g., Harris & D’Abramo 2015).

Multiple images of the same field are obtained with some intervals to detect
moving objects in optical observations. Moving objects should appear in
different positions of the images. A short arc is obtained by connecting such
two sources, usually referred to as a tracklet. Connecting multiple tracklets
provides a longer track, leading to a more precise orbit determination of a
moving object.

Algorithms connecting tracklets have been developed so far. Moving Object
Processing System (MOPS; Denneau et al. 2013, Kubica et al. 2007) is the
algorithm used in Pan-STARRS, utilizing a tree-based structure to efficiently
connect inter-night tracklets. ZTF’s Moving Object Discovery Engine (ZMODE;
Masci et al. 2019) is another implementation for Zwicky Transient Facility.
ZMODE constructs a "stringlet" (Waszczak et al. 2013) from three or more
detections, making the system more robust. HelioLinc provides a new idea to
this field, where tracklets are connected in a heliocentric frame instead of a
geocentric one. Although some algorithms are independent of tracklets (THOR;
Moeyens et al. 2021), extracting tracklets is the initial step in moving
object discovery.

The cadence of survey observations has increased with advances in
observational instruments (e.g., Pan-STARRS, ZFS, ATLAS, ASAS-SN, and
EvryScope; Chambers et al. 2016, Magnier et al. 2016, Dekany et al. 2020,
Tonry et al. 2018, Kochanek et al. 2017, Law et al. 2015). Video observation
is an extreme case (e.g., Tomo-e Gozen, OASES, and TAOS2; Sako et al. 2018,
Arimatsu et al. 2017, Huang et al. 2021, Lehner et al. 2018). An efficient
data reduction process is required due to the enormous amount of data in the
video observation. Parallel computing is one solution. Yanagisawa et al.
(2005) developed an FPGA board to extract faint tracklets from a sequence of
images. This paper presents another solution, developing an efficient
algorithm. The proposed algorithm extracts linearly aligned points in a three-
dimensional space, a fundamental routine to extract tracklets from video data.

The paper is organized as follows. The design and requirements of the proposed
algorithm are described in Section 2. Then, the performances of the algorithm
are illustrated in Section 3. Section 4 summarizes the paper. The algorithm we
develop is available as open-source software.

## 2\. Algorithm

This study aims to accelerate a process to identify moving object candidates
from a sequence of images. Many sophisticated applications are available to
extract sources from images (e.g., DAOFIND and Source Extractor; Stetson 1987,
Bertin & Arnouts 1996). The list of the extracted sources may contain fixed
stars, cosmic rays, and artificial noises, as well as possible moving objects.
It is not an easy task to isolate moving object candidates from such
distractors. This process can be a bottleneck in moving object extraction.

We developed a dedicated algorithm, Tracklet Extraction Engine (tracee), which
efficiently extracts moving object candidates from a source list. The tracee
is originally developed for an asteroid search but is possibly utilized in
other fields. Table A1 describes a basic usage of tracee.

### 2.1. Problem Setting

The algorithm we develop, tracee, is intended to deal with short video data.
Thus, we assume that the motions of moving objects are linear and uniform.
Thus, the problem is described as extracting linearly aligned points from a
point cloud in a three-dimensional space. A single data set may contain
multiple moving objects. The algorithm is required to detect them separately.
The moving objects possibly cross fixed stars and each other. The algorithm
should work properly in such cases.

Hough transformation (Hough 1962) a plausible algorithm to deal with the
problem, where each source votes for points in the hyperspace where each point
is associated with a line segment. Such voting-based algorithms are, however,
usually memory-consuming, while some efficient implementations are proposed
(Li et al. 1986). Thus, we do not adopt Hough transformation. Instead, we
split the problem into two parts; First, we construct a $k$-nearest neighbor
graph of the sources and then extract linearly aligned edges from the graph.
An overview of the procedures is presented in Algorithm 1. Detailed
descriptions are described below.

1 _Part 1: $k$-Nearest Neighbor Graph_

input : $V=\left\\{v_{i}\middle|_{i=1{\ldots}N}\right\\}$

output : $E=\left\\{(v_{i},v_{j})\middle|_{i,j\in\\{1{\ldots}N\\}}\right\\}$

2 Construct a $k$-NN graph $G(V,\,E)$ from $V$.

3 Merge the bidirectional edges in $E$.

4 Redirect the edges in the chronological order.

5 Remove inappropriate edges in $E$.

6 return _$E$_

7

8 _Part 2: Line Segment Grouping_

input : $E=\left\\{(v_{i},v_{j})\middle|_{i,j\in\\{1{\ldots}N\\}}\right\\}$

output : $B=\left\\{b_{m}\middle|_{m=1{\ldots}M}\right\\}$

9 Construct a set of baselines $B$ from $E$.

10 Remove short baselines from $B$.

11 Remove baselines with large scatter from $B$. return _$B$_

12

Algorithm 1 Overview of tracee

### 2.2. Procedures

#### 2.2.1. Input and Output

The tracee receives a list containing the source positions and the timestamps
of extraction. Hereafter, we call an element of the list a vertex. The input
data set $V$ is described as follows:

$V=\Bigl{\\{}v_{i}=\left\\{x_{i},\,y_{i},\,t_{i}\right\\}\Bigm{|}i=0,\ldots,N\Bigr{\\}},$
(1)

where $i$ is the index of the source, $v_{i}$ is the vertex corresponding to
the $i$th source, $x_{i}$ and $y_{i}$ are the source positions, $t_{i}$ is the
extraction timestamp, and $N$ is the total number of the extracted sources.

The tracklet is defined as a line segment or an edge. We define a baseline as
a data structure containing a line segment and associated vertices:

$b=\left\\{v^{s},v^{e},w\right\\},$ (2)

where $v^{s}$ and $v^{e}$ are respectively the starting and end points of the
line segment, $w$ contains the list of the vertices associated with the
baseline. The definitions of these elements are described below:

$\begin{cases}v_{s}=\left\\{x^{s},\,y^{s},\,t^{s}\right\\},\\\
v_{e}=\left\\{x^{e},\,y^{e},\,t^{e}\right\\},\\\
w=\left\\{\theta_{1},\,\theta_{2},\,\ldots,\,\theta_{K}\right\\},\end{cases}$
(3)

where $K$ is the number of the vertices associated with the baseline and
$\theta_{i}$ denotes the index of the vertex. The algorithm is expected to
return a set of baselines, $B$:

$B=\Bigl{\\{}b_{m}=\left\\{v^{\mathrm{s}}_{m},\,v^{\mathrm{e}}_{m},\,w_{m}\right\\}\Bigm{|}m=0,\ldots,M\Bigr{\\}},$
(4)

where $m$ is the index of the baseline and $M$ is the total number of the
baselines.

#### 2.2.2. $k$-Nearest Neighbor Graph

In the first part of the algorithm, we construct a $k$-nearest neighbor graph
($k$-NN graph) from the vertices. Every vertex of the $k$-NN graph has at
least $k$ edges to the $k$th nearest vertices. Samples of the $k$-NN graph are
presented in Figure 1. The blue dots represent the vertices. The solid and
dashed lines show the $k$-NN graphs for $k=1$ and $3$, respectively.

Fig. 1: A sample of $k$-nearest neighbor graph. The blue dots indicate the
vertices. The nearest neighbor graph ($k{=}1$) is denoted by the red thick
lines. The $3$-nearest neighbor graph is shown by the gray dashed lines.

A brute-force construction of a $k$-NN graph requires a cost of $O(n^{2})$,
which is not acceptable for large problems. Dong et al. (2011) presented NN-
Descent, an efficient algorithm to obtain an approximate $k$-NN graph, where
the construction cost is about $O(n^{1.14})$ and is suitable for parallel
computing. An overview of NN-Descent is described in Algorithm 2. The
algorithm receives the vertex set $V$ and the order of the graph $k$. The edge
list $E[v]$ handles the edges starting from $v$. The element of $E[v]$ is a
pair of the destination $w$ and the distance between $v$ and $w$. At first,
$E[v]$ is initialized with arbitrary $k$ vertices with infinity distances.
Then, the edge list $E$ is iteratively updated by replacing elements with
shorter ones. The algorithm stops when no element is updated.

input : vertex set $V$, order $k$

output : $k$-NN edge list $E$

1 foreach  _$v\in V$_ do // initialize $E$

2 $W\leftarrow$ arbitrary $K$ elements from $V$.

3 foreach  _$w\in W$_ do append $\langle w,\infty\rangle$ to $E[v]$.

4

5loop  __ // iteratively update $E$

6 $R\leftarrow$ reverse graph of $E$.

7 foreach  _$v\in V$_ do $\overline{E}[v]\leftarrow E[v]\cup R[v]$.

8 $c\leftarrow\mathit{False}$

9 foreach  _$v\in V$_ do

10 foreach  _$u_{1}\in\overline{E}[v]$ , $u_{2}\in\overline{E}[u_{1}]$_ do

11 $l\leftarrow$ distance between $v$ and $u_{2}$

12 $\langle\tilde{v},s\rangle\leftarrow$ largest element of $E[v]$.

13 if  _$l <s$_ then

14 pop $\langle\tilde{v},s\rangle$ from $E[v]$.

15 append $\langle u_{2},l\rangle$ into $E[v]$.

16 $c\leftarrow\mathit{True}$

17

18

19

20 if  _$c=\mathit{False}$_ then return _$E$_

21

Algorithm 2 NN-Descent

NN-Descent has been widely used, and there are already several
implementations. While major implementations are well-established and
functionally rich, high performance is required by tracee. Thus, we have
developed a minimal package to construct a $k$-NN graph efficiently in a
three-dimensional Euclidian space (Ohsawa 2020a). The core function of the
module is written in C++, and an interface for Python is provided. The
package, minimalKNN, is available in the Python Package Index as open-source
software.

The output of Algorithm 2 is a directed graph. The edges should be in
chronological order to trace moving objects. Thus, the bidirectional edges are
merged, and the edges are redirected in chronological order. We also remove
inappropriate edges whose corresponding velocities are too high. Then, the
updated $k$-NN graph is passed to further analysis.

#### 2.2.3. Line Segment Grouping

Linearly aligned edges of the graph are extracted to identify moving object
candidates. Jang & Hong (2002) tackled the problem of extracting favorable
line segments from a gray-scale image. The proposed algorithm is a fast line
segment grouping method; First, edges are extracted by an edge detector. Then,
the edges are split into short line segments (hereafter, elementary line
segments, ELSs). The algorithm they developed extracts a subset of linearly
aligned line segments from a set of ELSs. An overview of the algorithm is
described in Algorithm 3.

input : set of ELSs $E$

output : set of baselines $B$

1 construct an empty accumulator $A$.

2 foreach  _$e\in E$_ do // initialization

3 $\theta\leftarrow\mathrm{argument}(e)$

4 $c\leftarrow\mathit{False}$

5 foreach  _$b\in A[\theta]$_ do

6 if  _$e\sim b$_ then

7 append $e$ to the members of $b$

8 $c\leftarrow\mathrm{True}$

9

10 if  _$c=\mathit{False}$_ then

11 generate a baseline $b^{\prime}$ from $e$

12 append $b^{\prime}$ to $A[\theta]$.

13

14loop  __ // optimization

15 foreach  _$e\in E$_ do

16 $\theta\leftarrow\mathrm{argument}(e)$

17 $c\leftarrow\mathit{False}$

18 foreach  _$b\in A[\theta]$_ do

19 if  _$e\sim b$ & $e\not\in b$_ then

20 append $e$ to the members of $b$

21 $c\leftarrow\mathrm{True}$

22

23

24

25construct an empty baseline set $\overline{B}$

26 foreach  _$b\in B$_ do // merge baselines

27 $\theta\leftarrow\mathrm{argument}(b)$

28 foreach  _$\tilde{b}\in A[\theta]$_ do

29 if  _$b\sim\tilde{b}$_ then

30 $b\leftarrow\mathrm{merge}(b,\tilde{b})$

31 remove $b$ and $\tilde{b}$ from $B$

32

33

34 append $b$ into $\overline{B}$

35

36$B\leftarrow\overline{B}$

Algorithm 3 fast ELS grouping Fig. 2: A schematic view of the line segment
grouping criteria. The blue arrow indicates the baseline, while the short
black arrows indicate the elemental line segments.

Baselines and an accumulator play an essential role in facilitating line
segment grouping. The Baselines are line segment candidates obtained by
grouping colinear ELSs, while the accumulator is a data structure to search
baselines by the position angle. First, each ELS is compared with baselines in
the accumulator. Then, if the ELS and the baseline fulfill the similarity
criterion, the baseline is updated by embracing the ELS. Otherwise, a new
baseline is created from the ELS. Refer to Jang & Hong (2002) for the way to
create and update baselines. The definition of the similarity is illustrated
in Figure 2. The argument is the angle between the ELS and the baseline, the
lateral distance is the distance perpendicular to the baseline, and the gap
distance is the separation between the ELS and the baseline projected on the
baseline. Second, the same procedure is repeated one more time, but no new
baseline is created this time. Finally, similar baselines are merged into a
single baseline.

The original algorithm in Jang & Hong (2002) works on non-directional line
segments on the two-dimensional plane. Thus, we have extended the algorithm to
directional line segments in the three-dimensional space. The extended
algorithm is named Fast Directed Line Segment Grouping Method (fdlsgm). The
developed code is published as open-source software (Ohsawa 2020b). The core
function of the module is written in C++, and an interface for Python is
implemented.

The output of fdlsgm may contain unsuccessful baselines which are
stochastically grouped as lines. First, the baselines are removed when the
number of associated vertices is small. Then, the scatter of the vertices
around the baseline is evaluated, and the baselines with large scatter are
removed. The remaining baselines are finally returned as the candidates of
tracklets.

## 3\. Performance Verification

The performance of tracee is evaluated using mock data. In Section 3.1, we
demonstrate the way that the algorithm works. Tracklets are extracted in
several different conditions. The scalability of the algorithm is evaluated in
Section 3.2 with the different numbers of moving objects.

### 3.1. Validation with Mock data

Mock data are generated as follows; First, $n$ artificial moving objects are
generated in a field of $512{\times}512\,\mathrm{pixel}$. The velocities and
directions of the moving objects are randomly selected. Next, the positions of
the moving objects are measured for continuous 30 frames, while they are
disturbed assuming the uncertainty of the position measurement of
$\sigma=0.2\,\mathrm{pixel}$. Then, the measurements are stochastically
dropped with a probability of $p$. Finally, $m$ distractors are added to the
measurements.

The generated mock data are consistently processed with the same parameters.
In constructing the $k$-NN graph, the number of neighbors $k$ is set to 10,
but only the three shortest edges are adopted. Then, the edges faster than
$200\,\mathrm{pixel/frame}$ are removed. In the line segment grouping, the
argument threshold is set to $3^{\circ}$. The lateral distance threshold is
set to $1\,\mathrm{pixel}$. The gaps between baselines are accepted up to
three times the baseline lengths. Extracted tracklets are removed when they
have less than 10 sources.

Fig. 3: Mock data with different situations. The top panels show the data for
$(n,p,m)=(6,0,0)$. Panel (1a) shows the source positions projected on the
$XY$-plane, where the symbol colors indicate the frame number. Panel (1b)
illustrates the generated elemental line segments (ELSs, the thin black
arrows) and the extracted tracklets (the thick blue arrows). The middle and
bottom panels illustrate the data generated with $(n,p,m)=(6,0.5,0)$ and
$(6,0,500)$, respectively.

Fig. 4: A 3-dimensional views of Case 1 (top left), 2 (top right), and 3 (bottom). The source positions are shown by the circle symbols. The thin gray arrows indicates the ELSs. The retrieved tracklets are shown by the thick blue arrows. Table 1: Summary of Scalability Test $N_{\mathrm{obj}}$ | $\langle N_{\mathrm{track}}\rangle$ | $\langle N_{\mathrm{ELS}}\rangle$ | $\langle T_{\mathrm{ELS}}\rangle$ | $\langle T_{\mathrm{total}}\rangle$
---|---|---|---|---
$5$ | $5$ |  $617$$\pm$ | $17$ |  $16.6$$\pm$ | $0.7\,\mathrm{ms}$ |  $32.1$$\pm$ | $2.2\,\mathrm{ms}$
$10$ | $10$ |  $878$$\pm$ | $40$ |  $26.7$$\pm$ | $2.4\,\mathrm{ms}$ |  $60.3$$\pm$ | $6.6\,\mathrm{ms}$
$25$ | $24.8$ |  $1577$$\pm$ | $37$ |  $59.7$$\pm$ | $2.9\,\mathrm{ms}$ |  $134$$\pm$ | $5.2\,\mathrm{ms}$
$50$ | $49$ |  $2830$$\pm$ | $121$ |  $145$$\pm$ | $7.7\,\mathrm{ms}$ |  $356$$\pm$ | $31\,\mathrm{ms}$
$100$ | $98.2$ |  $5272$$\pm$ | $78$ |  $391$$\pm$ | $27\,\mathrm{ms}$ |  $1.05$$\pm$ | $0.05\,\mathrm{s}$
$125$ | $117.6$ |  $6505$$\pm$ | $167$ |  $539$$\pm$ | $28\,\mathrm{ms}$ |  $1.56$$\pm$ | $0.09\,\mathrm{s}$
$150$ | $136.6$ |  $7611$$\pm$ | $53$ |  $755$$\pm$ | $25\,\mathrm{ms}$ |  $2.13$$\pm$ | $0.10\,\mathrm{s}$

Mock data of $n=6$ are illustrated in Figure 3. Panels (1a) and (1b)
illustrate the result of Case 1, generated with $(n,p,m)=(6,0,0)$. The source
distribution projected on the $XY$-plane is shown in Panel (1b). The ELSs
generated from the sources are illustrated by the thin black arrows in Panel
(1b), while the extracted tracklets are shown by the thick blue arrows. All
the six moving objects are successfully identified by tracee. A 3-dimensional
view of Case 1 is presented in Figure 4.

Panels (2a) and (2b) show the result of Case 2, generated with
$(n,p,m)=(6,0.5,0)$. The input moving objects are the same as in the previous
case, but about half of the data are randomly removed (see, Panel (2a)).
Although the number of ELSs decreases accordingly, all the tracklets are
successfully recovered. A 3-dimensional view of Case 2 is presented in Figure
4.

The result of Case 3, generated with $(n,p,m)=(6,0,500)$, is presented in
Panels (3a) and (3b). The moving objects are the same as in Case 1, while 500
distracting vertices are randomly appended. The total number of vertices is
680. Thus, a brute force approach will produce 230860 possible line segments.
On the other hand, the number of ELSs in Panel (3b) is 1217. The algorithm
reduces the number of segments to just 0.5% of those in the brute force
approach. The thick blue arrows indicate that all the moving objects are
successfully identified as well. A 3-dimensional view of Case 3 is presented
in Figure 4.

### 3.2. Scalability

The performance of tracee with different numbers of moving objects is
investigated. As in Section 3.1, mock data are generated with $n=5$, $10$,
$25$, $50$, $100$, $125$, and $150$, while $p$ and $m$ are fixed to 0 and 200,
respectively. For each n, five datasets are drawn with different random seeds.
All the datasets are processed with the same parameters as in Section 3.2. The
calculation was conducted on a laptop with Intel Core i7-6600U
($2.60\,\mathrm{GHz}$). The total elapsed time and the elapsed time for
creating the k-NN graph are measured using the %timeit command provided by
IPython (Perez & Granger 2007).

The results are summarized in Table 1, where $N_{\mathrm{obj}}$ is the number
of moving objects, $\langle N_{\mathrm{track}}\rangle$ is the mean number of
extracted tracklets, $\langle N_{\mathrm{ELS}}\rangle$ is the mean number of
ELSs, $\langle T_{\mathrm{ELS}}\rangle$ is the mean elapsed time for creating
the $k$-NN graph, and $\langle T_{\mathrm{total}}\rangle$ is the mean total
elapsed time. In general, the moving objects are successfully identified in
every case. Some objects are missed since they are generated around edges and
shortly move outside. The detection rate slightly decreases for larger
$N_{\mathrm{obj}}$, mainly because similar tracklets are wrongly merged. Such
tracklets can be distinguished by tuning the threshold parameters, but this is
beyond the scope of this paper.

Fig. 5: Dependency of the elapsed time on the number of moving objects. The
red circles show the total elapsed times, while the black squares show the
elapsed times for creating the $k$-NN graph. The dashed and dot-dashed lines
indicate that $t\propto N_{\mathrm{ELS}}^{1.5}$.

Figure 5 shows the elapsed times against the number of the elemental line
segments, which is the most appropriate indicator of the problem size. The red
circles show the total elapsed times, while the black squares show the elapsed
times for generating the $k$-NN graph. Both elapsed times roughly follow
$t\propto N_{\mathrm{ELS}}^{1.5}$, as shown by the dashed and dot-dashed
lines. The figures below the symbols denote the numbers of moving objects.
Since $N_{\mathrm{ELS}}$ is almost proportional to $N_{\mathrm{obj}}$, the
elapsed times approximately follow $t\propto N_{\mathrm{obj}}$. The same holds
for the number of distractors. Thus, Figure 5 indicates that the elapsed times
increase at most with $N^{1.5}$, where $N$ is the representative size of a
problem. There is, however, an excess in the total elapsed time around
$N_{\mathrm{ELS}}\sim 8000$. The excess is possibly attributed to the
accumulator. The performance of the accumulator may decrease for such a large
$N_{\mathrm{ELS}}$. More efficient implementation of the accumulator will
improve the performance of tracee for larger problems

### 3.3. Application to Real Data

Finally, we cite an application of tracee in the Tomo-e Gozen transient survey
to attest that the algorithm can deal with actual observational data. Tomo-e
Gozen is a wide-field video camera developed in Kiso Observatory, the
University of Tokyo, capable of monitoring a sky of 20 square degrees at up to
2 fps (Sako et al. 2018). Kiso Observatory conducts a transient survey using
Tomo-e Gozen. The survey is intended to detect short transient objects in the
entire observable sky. Tomo-e Gozen obtains 6- or 9-second video data in every
pointing with changing observation fields to sweep the entire sky.

We have developed a data reduction pipeline to extract moving objects in the
video data obtained by Tomo-e Gozen. The tracee’s parameters are tuned to
detect near-earth objects with apparent speeds of $v\sim
1^{\prime\prime}\mathrm{s^{-1}}$. The obtained data are automatically
processed by dedicated computers installed on Kiso Observatory within a night.
The reduction pipeline successfully detects thousands of moving objects a
night, including asteroids, artificial satellites, and space debris. From
March 2019 to May 2021, 28 near-earth asteroids have been discovered in the
survey, showing the applicability of tracee for actual observational data.
Detailed analysis of this pipeline’s performance will be presented in a
forthcoming paper (Ohsawa et al., in prep).

## 4\. Conclusion

We have developed an efficient algorithm, tracee, to extract linearly aligned
points in a three-dimensional space. The algorithm will accelerate identifying
tracklets from short video data, which is a fundamental routine in moving
object detection.

The algorithm comprises two steps: creating a $k$-nearest neighbor ($k$-NN)
graph and grouping elemental line segments (ELSs). The first part utilizes an
efficient approximate $k$-NN graph construction method, NN-Descent (Dong et
al. 2011). To compose the second part, we extend the fast line segment
grouping method (Jang & Hong 2002) to a three-dimensional space. The algorithm
successfully identifies tracklets even when data are randomly decimated or are
contaminated by distractors. We have confirmed that the algorithm works
efficiently; the total elapsed time is approximately proportional to
$N^{1.5}$, where $N$ is a representative size of the problem. There is,
however, room for improvement for larger problems.

The algorithm is already implemented in the moving object detection system of
the Tomo-e Gozen transient survey. Thanks to the high performance of tracee,
obtained data are processed almost in real-time. As of June 2021, 28 near-
earth asteroids have been discovered. Although tracee is originally developed
to detect asteroids, artificial satellites, and space debris from astronomical
video data, the algorithm is potentially used in other fields, such as tracing
ejecta’s movement in an impact experiment.

The core functions of tracee are written in C++, and the interfaces for Python
are implemented. tracee itself is implemented in Python and is made public as
open-source software under the MIT license. The source code is hosted in a
Bitbucket repository222https://bitbucket.org/ryou_ohsawa/tracee/src/master/,
and the package is available in the Python Package Index, PyPI (Ohsawa 2021).

## Acknowledgments

This research has been partly supported by Japan Society for the Promotion of
Science (JSPS) Grants-in-Aid for Scientific Research (KAKENHI) Grant Numbers
18K13599.

## References

  * Arimatsu et al. (2017) Arimatsu, K., Tsumura, K., Ichikawa, K., et al., Organized Autotelescopes for Serendipitous Event Survey (OASES): Design and performance, Publications of the Astronomical Society of Japan, 69 (2017).  doi: 10.1093/pasj/psx048
  * Bertin & Arnouts (1996) Bertin, E., & Arnouts, S., SExtractor: Software for source extraction., Astronomy and Astrophysics Supplement Series, 117 (1996), 393.  doi: 10.1051/aas:1996164
  * Bottke et al. (2002) Bottke, W. F., Morbidelli, A., Jedicke, R., et al., Debiased Orbital and Absolute Magnitude Distribution of the Near-Earth Objects, Icarus, 156 (2002), 399.  doi: 10.1006/icar.2001.6788
  * Chambers et al. (2016) Chambers, K. C., Magnier, E. A., Metcalfe, N., et al., The Pan-STARRS1 Surveys, ArXiv e-prints, 1612 (2016), arXiv:1612.05560.  https://ui.adsabs.harvard.edu/abs/2016arXiv161205560C/abstract
  * Dekany et al. (2020) Dekany, R., Smith, R. M., Riddle, R., et al., The Zwicky Transient Facility: Observing System, Publications of the Astronomical Society of the Pacific, 132 (2020), 038001.  doi: 10.1088/1538-3873/ab4ca2
  * Denneau et al. (2013) Denneau, L., Jedicke, R., Grav, T., et al., The Pan-STARRS Moving Object Processing System, Publications of the Astronomical Society of the Pacific, 125 (2013), 357.  doi: 10.1086/670337
  * Dong et al. (2011) Dong, W., Moses, C., & Li, K., in Proceedings of the 20th international conference on World wide web, WWW ’11, (Hyderabad, India: Association for Computing Machinery), (2011), 577–586.  https://doi.org/10.1145/1963405.1963487
  * Granvik et al. (2018) Granvik, M., Morbidelli, A., Jedicke, R., et al., Debiased orbit and absolute-magnitude distributions for near-Earth objects, Icarus, 312 (2018), 181.  doi: 10.1016/j.icarus.2018.04.018
  * Harris & D’Abramo (2015) Harris, A. W., & D’Abramo, G., The population of near-Earth asteroids, Icarus, 257 (2015), 302.  doi: 10.1016/j.icarus.2015.05.004
  * Hough (1962) Hough, P. V. C., Method and means for recognizing complex patterns, (1962).  http://www.google.com/patents/US3069654
  * Huang et al. (2021) Huang, C.-K., Lehner, M. J., Granados Contreras, A. P., et al., The TAOS II Survey: Real-time Detection and Characterization of Occultation Events, Publications of the Astronomical Society of the Pacific, 133 (2021), 034503.  doi: 10.1088/1538-3873/abd4bc
  * Jang & Hong (2002) Jang, J.-H., & Hong, K.-S., Fast line segment grouping method for finding globally more favorable line segments, Pattern Recognition, 35 (2002), 2235.  doi: 10.1016/S0031-3203(01)00175-3
  * Kochanek et al. (2017) Kochanek, C. S., Shappee, B. J., Stanek, K. Z., et al., The All-Sky Automated Survey for Supernovae (ASAS-SN) Light Curve Server v1.0, Publications of the Astronomical Society of the Pacific, 129 (2017), 104502\.  doi: 10.1088/1538-3873/aa80d9
  * Kubica et al. (2007) Kubica, J., Denneau, L., Grav, T., et al., Efficient intra- and inter-night linking of asteroid detections using kd-trees, Icarus, 189 (2007), 151.  doi: 10.1016/j.icarus.2007.01.008
  * Law et al. (2015) Law, N. M., Fors, O., Ratzloff, J., et al., Evryscope Science: Exploring the Potential of All-Sky Gigapixel-Scale Telescopes, Publications of the Astronomical Society of the Pacific, 127 (2015), 234.  doi: 10.1086/680521
  * Lehner et al. (2018) Lehner, M. J., Wang, S.-Y., Reyes-Ruíz, M., et al., Status of the Transneptunian Automated Occultation Survey (TAOS II), 10700 (2018), 107004V.  doi: 10.1117/12.2309584
  * Li et al. (1986) Li, H., Lavin, M. A., & Le Master, R. J., Fast Hough transform: A hierarchical approach, Computer Vision, Graphics, and Image Processing, 36 (1986), 139.  doi: 10.1016/0734-189X(86)90073-3
  * Magnier et al. (2016) Magnier, E. A., Chambers, K. C., Flewelling, H. A., et al., The Pan-STARRS Data Processing System, arXiv e-prints, 1612 (2016), arXiv:1612.05240.  http://adsabs.harvard.edu/abs/2016arXiv161205240M
  * Masci et al. (2019) Masci, F. J., Laher, R. R., Rusholme, B., et al., The Zwicky Transient Facility: Data Processing, Products, and Archive, Publications of the Astronomical Society of the Pacific, 131 (2019), 018003.  doi: 10.1088/1538-3873/aae8ac
  * Moeyens et al. (2021) Moeyens, J., Juric, M., Ford, J., et al., THOR: An Algorithm for Cadence-Independent Asteroid Discovery, arXiv:2105.01056 [astro-ph] (2021).  http://arxiv.org/abs/2105.01056
  * Ohsawa (2020a) Ohsawa, R., minimalKNN: MinimalKNN: minimal package to construct k-NN Graph – ver. 0.3, (2020a).  https://pypi.org/project/minimalKNN/
  * Ohsawa (2020b) —, fdlsgm: FDLSGM: Fast Directed Line Segment Grouping Method – ver. 0.5.6, (2020b).  https://pypi.org/project/fdlsgm/
  * Ohsawa (2021) —, tracee: Tracklet Extraction Engine – ver. 0.0.3, (2021).  https://pypi.org/project/tracee/
  * Perez & Granger (2007) Perez, F., & Granger, B. E., IPython: A System for Interactive Scientific Computing, Computing in Science Engineering, 9 (2007), 21.  doi: 10.1109/MCSE.2007.53
  * Sako et al. (2018) Sako, S., Ohsawa, R., Takahashi, H., et al., in Proc. SPIE, Vol. 10702, (International Society for Optics and Photonics), (2018), 107020J.  https://doi.org/10.1117/12.2310049
  * Stetson (1987) Stetson, P. B., DAOPHOT - A computer program for crowded-field stellar photometry, Publications of the Astronomical Society of the Pacific, 99 (1987), 191.  doi: 10.1086/131977
  * Tonry et al. (2018) Tonry, J. L., Denneau, L., Heinze, A. N., et al., ATLAS: A High-cadence All-sky Survey System, Publications of the Astronomical Society of the Pacific, 130 (2018), 064505.  doi: 10.1088/1538-3873/aabadf
  * Waszczak et al. (2013) Waszczak, A., Ofek, E. O., Aharonson, O., et al., Main-belt comets in the Palomar Transient Factory survey - I. The search for extendedness, Monthly Notices of the Royal Astronomical Society, 433 (2013), 3115.  doi: 10.1093/mnras/stt951
  * Yanagisawa et al. (2005) Yanagisawa, T., Nakajima, A., Kadota, K.-I., et al., Automatic Detection Algorithm for Small Moving Objects, Publications of the Astronomical Society of Japan, 57 (2005), 399.  doi: 10.1093/pasj/57.2.399

Table A1: A short example of tracee

⬇

1#!/usr/bin/env python

2# -*- coding: utf-8 -*-

3import numpy as np

4import tracee

5

6# Load the data table.

7# The table should have three columns.

8filename = ’sample/mockdata_N006F030D500d00_b7e8.txt’

9data = np.loadtxt(filename)

10

11# Generate a parameter set.

12param = tracee.default_parameters()

13param.limit = 10 # Set the minimum number of points to 10.

14

15# Call tracee.extract to identify tracklets.

16# The function returns a list of Tracklet instances.

17# The Tracklet instance contains

18# - tail: the starting point.

19# - head: the terminal point.

20# - members: a list of the associated points.

21tracklet = tracee.extract(data, n_neighbor=3, param=param)

††footnotetext: ∗1Institute of Astronomy, Graduate School of Science, The
University of Tokyo, 2-21-1 Osawa, Mitaka, Tokyo 181-0015, Japan
<EMAIL_ADDRESS>