# Measurement and Data-Assisted Simulation of Bit Error Rate in RQL Circuits

Quentin Herr, Alex Braun, Andrew Brownfield, Ed Rudman, Dan Dosch, Trent
Josephsen, and Anna Herr  Northrop Grumman Corp., Baltimore, MD 21240

(14 April 2021)

###### Abstract

A circuit-simulation-based method is used to determine the thermally-induced
bit error rate of superconducting logic circuits. Simulations are used to
evaluate the multidimensional Gaussian integral across noise current sources
attached to the active devices. The method is data-assisted and has predictive
power. Measurement determines the value of a single parameter, effective noise
bandwidth, for each error mechanism. The errors in the distributed networks of
comparator-free RQL logic nucleate across multiple Josephson junctions, so the
effective critical current is about three times that of the individual
devices. The effective noise bandwidth is only 6-23% of the junction plasma
frequency at a modest clock rate of 3.4 GHz, which is 1% of the plasma
frequency. This analysis shows the ways measured bit error rate comes out so
much lower than simplistic estimates based on isolated devices.

Digital superconducting is a long-standing candidate for beyond-CMOS
technology due to high clock rates and unparalleled power efficiency Herr et
al. (2011)-Vernik et al. (2016). Demonstrations of digital functions continue
to mature Herr et al. (2013), and are currently at the level of small CPUs
Ayala et al. (2021). Fundamental power advantages derive from both the
Josephson junction active devices and non-dissipative interconnects. In
contrast to CMOS, superconducting technology is thermally limited not device
limited, meaning the devices are sized based on bit-error rate (BER)
limitations, not based on lithographic minimum feature size. Current energy-
efficient variants of superconducting digital logic, such as RQL and the QFP,
have scaled the energy per switching event to within a factor of 100-1000
above Landauer’s limit, $\ln(2)k_{B}T$.

The penalty for such performance is more stringent optimization criteria. The
circuits need to be characterized not only by timing design, as with CMOS, but
also in terms of parametric operating margins and BER performance. Parametric
margins are determined using noise-free circuit simulations, but the more
relevant question is to determine parametric margins defined in terms of an
acceptable BER. For large scale applications, the acceptable BER for
individual gates is on order $10^{-24}$. These levels are difficult to access
in either simulation or measurement.

Elevated BER can be measured as a function of a tuning parameter, and
extrapolated to the region of unobservable levels. This approach has been
widely reported Herr and Feldman (1996)-Takeuchi et al. (2017). The usual
caveats with extrapolation apply, as there are multiple sources of BER in the
circuits. Regardless of the error mechanism, BER scales simply with energy set
by the device size Herr et al. (2011). While measurement is useful and
necessary, a simulation-based approach is also needed.

Models of BER exist for only a few simple cases. Analysis of the comparator
Filippov et al. (1995) predicts how the BER scales with clock rate in the low-
speed limit that might be applicable to the QFP Takeuchi et al. (2017), but
not more generally. Spontaneous switching of biased, isolated junctions is
understood Klein and Mukherjee (1982), but has not been generalized to the
distributed networks of SFQ circuits.

Simulation methods are also of limited utility. Fokker-Plank simulation has
been applied to the comparator Herr and Feldman (1997), but this approach is
prohibitive for larger systems. The only alternative is a Monte-Carlo method
requiring repeated circuit simulations with random sources for the noise
Satchell (1999). The method is generally applicable to any circuit schematic,
but is low resolution and numerically intensive.

We present a new simulation-based method that is a data-assisted multivariate
integration. The method repurposes the integral for parametric yield to find
BER:

  * •

Parametric Yield is the integral of the Gaussian-distributed parameters over
the operating region of the circuit. This gives the probability of working
circuits.

  * •

Bit Error Rate is the integral of the Gaussian-distributed noise currents over
the operating region of the circuit. This gives the probability of working
clock cycles.

A single free parameter, effective noise bandwidth, is determined for each
scenario by comparing simulation to measurement. The approach is generally
applicable to any circuit schematic and any noise-induced error mechanism
associated with Single-Flux-Quantum (SFQ) circuits. The method is
deterministic and can calculate arbitrarily small error probabilities with
high resolution. The method is efficient in terms of circuit simulations,
requiring about $3^{N}$ margin calculations for $N$ noise sources. Noise
sources are included no more than eight at a time, but a sliding window of
inclusion covers larger circuits.

BER simulation can be used to improve parametric optimization in the design
phase. An important feature here is to ability to calculate individual margins
(and BER) as an intersection across global parametric corners. At each corner
parameter set, margins are calculated in parallel, and the final number is the
most pessimistic result. This approach could be used to calculate the most
pessimistic BER across global parameter mistargeting, or across signal input
timing. This is adjacent to the statistical timing analysis of advanced-node
CMOS, see e.g. Kahng (2015).

The rest of the paper covers simulation-based numerical evaluation of the
multivariate Gaussian integral, simulated BER of two representative logic
gates, and measured BER and comparison to the simulation. The data-assisted
method uses a generic value for effective bandwidth in the initial
simulations, and then solves for the measured values. The discussion centers
on the physical meaning of the effective noise bandwidth.

##  I Multivariate Gaussian Integral

BER is the probability of failure, which is given by the complement of yield.
This is the integral over the tails of the Gaussian distribution, outside the
operating region of the circuit. We start with the one dimensional case and
generalize to higher dimensions. In the simplest case the upper and lower
margins of the circuit are equal. Normalized margin $r=m/\sigma$ is the
circuit operating margin $m$, normalized in units of the standard deviation.
In this case

$\mbox{yieldc}(r)=\mbox{erfc}\\!\left(r/\sqrt{2}\right)$

The upper and lower margins, $r_{a}$ and $r_{b}$, are likely different. If so,
the contributions can be computed separately, normalized, and summed.

$\mbox{yieldc}(1,r_{a},r_{b})=1/2\,\mbox{erfc}\\!\left(r_{a}/\sqrt{2}\right)+1/2\,\mbox{erfc}\\!\left(r_{b}/\sqrt{2}\right)$

In $N$ dimensions, analytic results obtain if the operating region is defined
by a radius $r$.

$\mbox{yieldc}(N,r)=\mbox{Q}(N/2,r^{2}/2)$

where $\mbox{Q}(a,x)=\Gamma(a,x)/\Gamma(a)$, is the normalized upper
incomplete gamma function as defined e.g. in Press et al. (1992a). This is
also known as the regularized gamma function. Here the limits of integration
correspond to a constant value of the Gaussian joint probability distribution,
which has radial symmetry.

Figure 1: The operating region of the circuit, shaded, overlays the Gaussian
joint probability distribution, shown as concentric isocontours equally spaced
in units of sigma. The operating region is approximated by points on the
operating boundary, organized as simplexes (line segments in the two
dimensions shown). The simplex defined by points Q1 and Q2 subtends an angle
$\Omega_{s}$. The mean value of the Q-function for these points, weighted by
the angle, is one term in the Riemann sum that approximates the Gaussian
integral over the operating region.

The operating region of the circuit generally does not have radial symmetry
and must be mapped out. This is illustrated for two dimensions in Fig. 1, and
generalizes to higher dimensions. We approximate the operating region by
connecting boundary points with simplexes. Each simplex $s$ gives a yield
estimate based on the mean value $\langle\mbox{Q}_{s}\rangle$ of the $Q$
values evaluated at the boundary points. This estimate is weighted by the
angle $\Omega_{s}$ subtended by the segment. The integral is approximated by a
normalized Riemann sum of these terms. In $N$ dimensions,

$\mbox{yieldc}=\frac{1}{\Omega_{N}}\sum_{s}\Omega_{s}\langle\mbox{Q}_{s}\rangle$

which is normalized to the total angle $\Omega_{N}$. The mean value of Q for
each simplex is

$\langle\mbox{Q}_{s}\rangle=\frac{1}{N}\sum_{i=1}^{N}\mbox{Q}(N/2,r_{t[s,i]}^{2}/2)$

Simplexes are indexed by $s$. For a given simplex, $r_{t[s,i]}$ returns the
value of radius, indexed by $i$, for each of the points.

Details of the algorithm are described in Appendix 1. Including calculation of
the angle $\Omega_{s}$, the annealing schedule of the adaptive algorithm that
adds new points to the operating boundary, and simplex fracturing to create a
finer grid.

The algorithm does not require the operating region to be convex, which is a
fundamental constraint in simplicial design centering Director and Hachtel
(1977); Herr and Johnson (2001). Here it is only required that the operating
region be single-valued as viewed from the origin, which corresponds to the
binary search vectors. The value of the integral is dominated by regions of
the operating boundary nearest the origin. This implies that the computational
intensity is similar to finding global minima by exhaustive search. In
practice, covering the space exhaustively requires about $3^{N}$ margin
calculations. This can be understood as the set of all search vectors for
which each dimension has a value of $+1$, $-1$, or $0$. This set captures all
of the potential dependencies of the space and of all subspaces. The number of
simplexes grows rapidly as points are added, which currently imposes a
practical limit of about eight dimensions.

##  II BER Simulation

In simulation, an auxiliary dc current source is applied across each junction
in the circuit. The current through each source is a circuit parameter, with
nominal value set to zero and sigma equal to rms noise current,

$I_{\mbox{{\small rms}}}=\sqrt{\frac{4k_{B}TI_{c}\beta}{\Phi_{0}}}$

which scales with junction critical current, $I_{c}$. The expression derives
from the Johnson noise, $\sqrt{4k_{B}TB/R}$ using the junction characteristic
impedance, $R=\sqrt{L_{J}/C_{J}}$, plasma frequency,
$B=1/(2\pi\sqrt{L_{J}C_{J}})$, and inductance, $L_{J}=\Phi_{0}/(2\pi I_{c})$.
The bandwidth $\beta$ is a unitless fraction of the plasma frequency. We will
use the effective bandwidth $\beta$ as a fitting parameter to relate the
simulation result to measured data. This expression for noise current does not
depend on junction capacitance, $C_{J}$ or shunt resistance.

The overall method is 1) choose an initial value for $\beta$ to simulate BER,
2) compare the simulated result to measured data to find the experimentally-
derived effective $\beta$ for each error regime, and 3) use this value in
subsequent simulations. All BER simulations in this paper used the initial
value $\beta=0.25$.

On the way to evaluating the Gaussian integral, the algorithm reports the
critical search vector, directed towards the point on the operating boundary
found to be nearest the origin. This indicates which sources contributed most
to nucleating the error. The critical vector is suggestive but not definitive.
A gate e.g. with symmetric inputs would have equally critical vectors on both,
but only one could be reported. However, the algorithm would integrate over
all paths to calcualte BER.

It is intractable and unnecessary to include all noise sources at once in the
BER simulation. Instead, it is enough to include sources that contribute to
nucleation of the error. Simulations proceed with inclusion 7-8 noise-current
parameters at a time, chosen among contiguous junctions. We use a sliding
window, meaning that the parameter-inclusion sets overlap. Each window returns
a BER. The most relevant window is the one that returns the highest BER.

Table 1: Critical vectors for the points indicated in the AND gate simulation of Fig. 3a, illustrating three different error mechanisms. Columns correspond to noise sources on the junctions of Fig. 2a |  | Input A | Input B | Output
---|---|---|---|---
Point | Window | J0 | J1 | J2 | J3 | J4 | J5 | J6 | J7 | J8 | J9 | J10
a | 1 |  $-$0.271 |  $-$0.924 |  $-$0.271 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | - | - | -
b | 1 | 0.197 | 0.558 | 0.197 | 0.279 | 0.674 | 0.279 | 0.000 | 0.000 | - | - | -
c | 2 | - | - | 0.163 | - | - | 0.000 | 0.543 | 0.774 | 0.231 | 0.163 | 0.000
Figure 2: Circuit schematics are shown for a) the AND gate, b) the DFF gate,
and c) the JTL subcircuit. The critical currents of the junctions, $I_{c}$ are
given in units of $\mu$A. JTL junctions are biased with an AC sinusoid and a
DC offset via mutual inductance to L2. The signal inductors, including L3,
typically have values ranging from 0.33-0.5 $\Phi_{0}/I_{c}$. The storage
inductors L0 and L1, and the bias inductors L2, are larger. The AC bias is
applied globally, including the input and output amplifier stages. The DC bias
is applied locally to the device under test via a separate control line.

We applied the algorithm to the RQL circuits shown in Fig. 2. For present
purposes, the AND gate is representative of gate implementations that do not
have a Josephson comparator, and the DFF serves as a diagnostic for
comparator-based gates, including RSFQ and the QFP. The AND gate Braun and
Harms (2018) is based on three-input majority, with one input tied to ground.
This is analogous to QFP logic, but implementation in terms of data encoding,
interconnect, and clock phasing are distinct. The RQL implementation is low-
latency as it does not require advance of the clock phase to prevent back-
traveling pulses on the inputs Braun (2018); multiple gates can be cascaded on
a single phase. The D flip-flip (DFF) stores the input until it is clocked out
through the comparator. The implementation is similar to the RSFQ DRO.
However, both positive and negative polarity pulses are used in RQL, so the
stored signal may be of either polarity. The utility of the DFF and other
features of the RQL library are beyond the scope of BER considerations, and
will be described elsewhere.

Figure 3: Simulated BER of the AND gate as a function of DC level, $x$, and
normalized AC amplitude, $A$. a) Simulations (points) for each value of $A$
are connected with lines to guide the eye. Gaps in the line are where the
maximum BER moved from one sliding window to the other. Two sliding windows
were used for inclusion of the noise current sources. The points (a), (b), and
(c) are called out for further analysis. b) Simulated points replotted, now
with curves defined by Eqn. 2 that captures the result in functional form. c)
The function of Eqn. 2 plotted as a contour map. The outer contour is for a
BER of 0.5, which equates to noise-free margins. The horizontal blue line
marks a cross-section corresponding to the blue line in the upper panels. Each
contour has three sides (a), (b), and (c) representing three distinct error
mechanisms.

The BER calculation at each set point requires a few thousand binary searches
across multiple windows. However, simulations can proceed in parallel, so full
characterization of the gate requires less than 24 hours of real time using a
few large servers running WRspice Whiteley (2020).

Simulated BER of the AND gate is shown Fig. 3a. Three sets of curves are
visible; the progression with negative slope in the left, and two progressions
of positive slope on the right. All of this can be expressed analytically as
the sum of three error functions, with fitting coefficients that depend on the
AC amplitude, $A$. The fit, detailed below, produced the contour plot shown in
Fig. 3c.

The three-sided contours correspond to typical JTL-based error mechanisms. The
DC offset optimally produces symmetry between positive and negative SFQ pulses
by putting a $\Phi_{0}/2$ flux bias on the bias inductor (L2 in Fig. 2c). AC
amplitude powers the transistions. When DC is low (side a), positive pulses
fail to propagate and are annhiliated by the trailing negative pulse. When DC
is high and AC is low (side b), it is the trailing negative pulse that fails
to propagate. When DC and AC are both high (side c), positive pulses are
spontaneously generated in error. By symmetry, one might expect that DC low
and AC high would produce a fourth regime where negative pulses were generated
in error. The asymmetry is in the data encoding. Every positive pulse is
followed half a cycle later by a negative pulse that serves as a reset.
Spontaneous negative pulses that anticipate the transistion do not register as
an errors. This extends the operating region of the circuit up and to the left
well beyond normal design limits.

In the AND gate, the three error mechanisms may arise in different parts of
the circuit. This is illustrated for the three points (a), (b), and (c) called
out in Fig. 3a. The critical vectors for these points are entered in Table 1.
Point (a) is centered on one of the input JTLs, point (b) straddles both
inputs, and point (c) is centered on the output. For each case, the table
shows the dominant sliding window of parameter inclusion.

It would be possible—but needlessly intensive—to run and rerun the BER
simulations for different values of effective bandwidth in order to match the
experimentally measured result. Instead, we develop a functional fit to the
simulations that incorporates the bandwidth dependance. For each value of $A$,
the simulation points were partitioned and fit to one of three error
functions, using margin and noise coefficients. The total BER is given as the
sum of these three terms.

$\displaystyle\mbox{BER}(x,A,\beta_{a},\beta_{b},\beta_{c})=$
$\displaystyle\frac{1}{2}\mbox{erfc}\\!\left[\frac{x-m_{a}(A)}{\sqrt{2\beta_{a}}n_{a}(A)}\right]$
$\displaystyle+\frac{1}{2}\mbox{erfc}\\!\left[\frac{m_{b}(A)-x}{\sqrt{2\beta_{b}}n_{b}(A)}\right]+$
$\displaystyle\frac{1}{2}\mbox{erfc}\\!\left[\frac{m_{c}(A)-x}{\sqrt{2\beta_{c}}n_{c}(A)}\right]$
(1)

The three similar terms fit the (a), (b) and (c) curves. For the first term,
the fitting parameter $m_{a}(A)$, corresponds to noise-free margin which
determines the offset along the $x$-axis. The term $\sqrt{\beta_{a}}n_{a}(A)$
corresponds to rms noise, with the dependance on effective noise bandwidth,
$\beta_{a}$, made explicit. All of the curves are well-characterized by a
single function using fitting coefficients that are linear functions of $A$.

$m_{a}(A)=Am_{1a}+m_{0a}\mbox{,}\quad n_{a}(A)=An_{1a}+n_{0a}$

Table 2: Coefficients for the function of Eqn. 1 fit to the AND gate simulation points. | $m_{1\\_}$ | $m_{0\\_}$ | $n_{1\\_}$ | $n_{0\\_}$
---|---|---|---|---
a |  $-$7.724 | 7.542 | 0 | 0.1760
b | 7.732 |  $-$1.650 | 0 | 0.1240
c |  $-$10.173 | 16.151 | 0.0655 | 0.1480

Fit values for the three curves are entered in Table 2. Note that the slopes
of curves (a) and (b) are constant across the range of $A$ values. The
resulting function

$\mbox{BER}(x,A,\beta_{a}\mbox{=}0.25,\beta_{b}\mbox{=}0.25,\beta_{c}\mbox{=}0.25)$
(2)

is a good fit to all of the simulation points, as shown in Fig. 3b. The
exception is that the positive-slope progressions for $A=\\{1.188,1.259\\}$
are above the line. Further investigation showed that these were over-bias
errors in the output JTL, far from the gate itself. These errors are real, but
are outside of the gate characterization.

Figure 4: Simulated BER for the DFF gate as a function of the local DC level
and normalized AC amplitude, $A$. Four sliding windows were used, centered on
each of the inputs, the output, and the gate itself. Points for each value of
$A$ are connected with lines. Gaps in the line are where the maximum BER moved
from one window to the other. All four windows are represented in the data for
$A=0.944$ (bold lines). The noise floor arises from switching errors in the
gate comparator.

We applied the same method to BER simulation of the DFF, shown in Fig. 4. Here
the waterfall curves are interrupted by a noise floor at about $10^{-40}$.
Further analysis showed that the floor corresponds to decision errors in the
comparator, while the waterfalls corresponds to errors in the JTLs surrounding
the gate. The floor is far below the limits of direct observation in
measurement. This simulation indicates that the AC amplitude and DC offset set
points, applied directly to the JTLs but not to the comparator itself, do not
allow exapolation to the dominant error mechanism at low BER. What is needed
is an auxillary current bias applied directly to the central node of the
comparator Herr and Feldman (1996); Filippov et al. (1995), as this would
produce a large shift in comparator threshold.

##  III BER Measurement and Comparison to Simulation

Integrated circuits containing the RQL gate library were designed into a six-
metal-layer fabrication process supplied by D-Wave Berkley et al. (2010). This
revision of the fab featured Josephson junctions with 100 $\mu$A/$\mu$m2
critical current density. The logic gates used individual circuits with
dedicated input stages and output amplifiers on-chip. The circuits shared a
global 3.4 GHz resonant clock network that provisioned the entire active area
of the chip.

Crosstalk between the clock and signal lines in the pressure-contact LHe dip
probe was a challenge, so the output data link was established using
differential signals, amplified by a pair of Miteq JSMF4-02K180-30-10P LNAs at
the probe head. 3 dB attenuators (50 $\Omega$) at the inputs of the LNAs were
used to improve the impedance match. These fed a Marki BAL-0026 balun that
produced a single-ended signal for the lab instruments. A Keysight J-BERT
M8020A produced the data patterns and counted the errors. This was
synchronized to a pair of Rohde & Schwarz SGS100A sources that powered the
clock network with I and Q signals. DC levels were generated by a Stahl BS
1-10.

Figure 5: Measured BER (points) as a function of DC offset. Error bars visible
for the lowest points correspond to binomial counting statistics. a) Five
different logic gates measured at an AC amplitude, $A=0.944$. Each curve is
fit to an error function to guide the eye. A noise floor is visible for the OR
gate. We attribute this to observed limitations of the output data link for
this particular case, and not to the gate itself. b) Additonal measurements of
the AND gate at several values of $A$. Measurements are fit to the simulation
result (lines) via Eqn. 3. c) The function of Eqn. 3 plotted as a contour map.
The outside contour is for a BER of 0.5, corresponding to noise-free margins.
The inside contour is for $0.5\times 10^{-110}$.

Measurement of five different logic gates is shown in Fig. 5a. The AND and OR
gates are closely related as they derive from the same majority gate. For the
OR, the third input is initialized to logical “1.” The Inverter and XOR Harms
et al. (2019) are also closely related; the Inverter is derived from XOR, with
one of the inputs initialized to logical “1.” BER for AND and OR are
coincident on the left, but offset on the right. BER for the Inverter and XOR
are nearly coincident on the right, but offset on the left. These offsets
might be inherent to the design and test vectors, or due to parametric
variations in fab or trapped-flux effects in test. Additional simulations and
test would be needed to resolve these questions. The main result is that the
slopes of the curves are consistent, reflecting that the observed errors are
induced in interconnect JTLs, which are similar among the designs.

Measured BER of the AND gate at different AC and DC set points, shown in Fig.
5b, mirrored the simulations. Curves fitting the simulation to the
measurement, also shown, used the function defined in Eqn. 1 with arguments

$\mbox{BER}(x\mbox{=}1.04x^{\prime},A\mbox{=}0.99A^{\prime},\beta_{a}\mbox{=}0.058,\beta_{b}\mbox{=}0.14,\beta_{c}\mbox{=}0.23)$
(3)

where $x^{\prime}$ and $A^{\prime}$ are the DC offset and AC amplitude scale
for the measured data. These numbers produce good quantitative agreement. The
factor of 1.04 indicates a small registration error on DC offset. This could
be accounted for by a 4% shift in mutual inductance to the control line. The
AC amplitudes for the measurement have an arbitrary scale, relative to
simulation, but the spacing of 0.5 dB is fixed for both. A single scaling
factor, 0.99, aligned the simulation to the measurement. These are small
disparities given that the simulation used nominal design values; no attempt
was made to incorporate global parametric targeting. The primary result lies
in the values for effective noise bandwidth. These numbers were chosen to be
0.25 in simulation, but came out widely divergent—and generally smaller—in
measurement.

Measured BER of the DFF were similar to the AND gate. This is unsurprising, as
simulation indicates that observable errors belong to the JTLs, not the gate
itself. However, the DFF comparator produced a BER floor in simulation. To
induce comparator errors at observable levels, an additional detuning bias
would be needed that directly shifts the comparator threshold. We would expect
the effective noise bandwidth for comparator errors to be higher than the
other error mechanisms, as the error does not depend on junction switching
time per se, but on a shorter time scale when the phase difference between the
junctions passes some threshold. Based on a review of previous work Herr and
Feldman (1997); Filippov et al. (1995), an effective normalized bandwidth of
0.5 is our best estimate. If so, the simulations using a bandwidth of 0.25
underestimated comparator errors, and the BER floor is actually around
$10^{-25}$ based on scaling given in Eqn. 1.

##  IV Discussion

Results of the previous section show that 1) operating margins at low BER are
generally wide enough to support complex RQL circuits. 2) BER in measurement
is less than in simulation, if effective noise bandwidth is taken to be the
Josephson junction plasma frequency, and 3) the effective noise bandwidth
depends on the error mechanism.

AC overbias errors, corresponding to curves (c) in Figs. 3 and 5, involve
spontaneous junction triggering that can be modeled using the Kramers escape
rate. This analysis gives a first-principles estimate without resort to an
effective noise bandwidth. The Kramers escape rate is $f\approx
f_{a}\exp\left[-\Delta U/(k_{B}T)\right]$, where $k_{B}T$ is the thermal
energy, $\Delta U$ is the potential barrier, and $f_{a}$ is the attempt
frequency. Here we can safely model the noise as purely thermal at 4.2 K,
because DC and AC currents are very weakly coupled to the circuit using
magnetic transformers. External noise scales as $k^{2}$, where $k$ is coupling
coefficient Herr et al. (2011).

The potential barrier for a single biased Josephson junction is approximately
Likharev (1986)

$\Delta
U(I_{b})\simeq\frac{\Phi_{0}}{2\pi}\frac{2I_{c}}{3}\left(2-\frac{2I_{b}}{I_{c}}\right)^{3/2}$

where the total bias current through the junction is the sum of AC and DC
components, $I_{b}=I_{\mbox{DC}}+I_{\mbox{AC}}$. At the nominal value
$I_{\mbox{DC}}=2.8$ mA, the externally-applied DC offset current produces a
bias current of only $I_{b}=0.24I_{c}$ through the junction. This gives the
transfer function $I_{b}/I_{c}=0.086x/\mbox{mA}$. The AC current
$I_{\mbox{AC}}$ shifts the BER function by an arbitrary offset—for comparing
to measured data this is left as a fitting parameter. The resulting Kramers
escape rate is

$\mbox{BER}(x)\simeq\alpha\exp\\!\left[\frac{\Phi_{0}I_{c}}{3\pi
k_{B}T}(2\\!-\\!2[0.086I_{DC}\\!+\\!I_{AC}]/\mbox{mA})^{3/2}\right]$ (4)

where the prefactor $\alpha=10$ is the number of attempts per clock cycle.
This value does not need to be precise for low BER values. The function
corresponds to the asymptotic form of erfc, and is valid in the region of low
BER. Fitting the measured data for overbias errors (the steeper curves on the
right of Fig. 5b) with Eqn. 4, using critical current and AC bias as fitting
parameters, results in $I_{c}\approx 110\,\mu$A.

The effective critical current indicated by the Kramers escape rate is about
three times larger than the critical current of the individual junctions used
in a circuit, suggesting that the error mechanism is distributed across
multiple junctions. This result comports nicely with the simulation result
shown as curve (c) in Table 1 with about three junctions involved in the
nucleation of overbias errors in the output JTL. The JTL inductances have an
$I_{c}L$ product of about $\Phi_{0}/3$, meaning that the three JTL junctions
span about one-$\Phi_{0}$ of interconnect.

The normalized effective bandwidth for overbias errors in measurement,
$\beta_{c}=0.23$, agrees well with initial simulations with $\beta_{c}=0.25$
and indicates a spontaneous-switching time that is long compared to the plasma
frequency. This simply means that junction switching time is longer at low
values of overbias, as observed in Harris (1979).

Annihilation errors, corresponding to curves (a) in Figs. 3 and 5, have a
different character. These errors arise when the leading, positive pulse in
the RQL data encoding fails to propagate and is annihilated by the trailing
negative pulse. Since the positive and negative pulses are separated in space
and time by a half-cycle, the noise must persist for a fair fraction of a
clock cycle in order to produce an error. This implies much lower effective
noise bandwidth. The measured value, $\beta_{a}=0.058$ corresponds to about
17% of the clock cycle, or 67% of the quarter-cycle of the four phase clock at
3.4 GHz clock and 340 GHz plasma frequency. Since noise bandwidth for
annihilation errors is determined by clock rate it is expected to increase
with clock rate, to be confirmed in future experiments.

Similar arguments exist for annihilation error corresponding to curve (b) in
Fig. 3-5, but here the trailing, negative pulse of the RQL data encoding fails
to propagate and is annihilated when there is a positive pulse on the next
cycle. Different effective bandwidths between curves (a) and (b) is
unsurprising as the data encoding is asymmetric, and as the errors arise in
different parts of the circuit, based on the critical vectors entered in Table
1.

## Conclusion

Here we have presented a framework to explain, predict, and quantify the BER
of RQL gates. The integral of the Gaussian-distributed noise currents
associated with the Josephson junctions is evaluated across the multi-
dimensional operating region of the circuit. Measurement determines the value
of a single parameter, effective noise bandwidth, for each error mechanism, in
a data-assisted approach. All this would apply equally well to the other
superconducting SFQ logic families.

The BER in combinational RQL gates such as the AND gate is governed by the
JTL-based error mechanisms, including spontaneous switching at overbias and
pulse annihilation at underbias. The effective noise bandwidth is quite low
for pulse annihilation errors, as it is based on the clock rate, not the
junction plasma frequency. The distributed nature of the SFQ pulse means that
multiple junctions are involved in nucleating the error for spontaneous
switching, so the effective device size is that of multiple devices in
parallel, in agreement with Klein and Mukherjee (1982). All this explains why
the measured BER extrapolates to $10^{-110}$, which is much lower than
predicted by simplistic estimates for isolated devices. In the long-junction
limit Averin et al. (2006), JTL interconnect can be virtually dissipation free
while maintaining negligible BER, as “the coupling between mechanical and
thermal modes vanishes” Fredkin and Toffoli (1982). Ultimately this may lead
reversible logic gates as well Herr et al. (2010); Osborn and Wustmann (2020).

The clocked comparator of the RQL DFF gate is representative of the other SFQ
logic families, including RSFQ and the QFP. BER simulation showed that the
comparator produced a noise floor, at about $10^{-25}$ using junctions with 50
$\mu$A critical current, as the comparator does involve isolated junctions and
higher noise bandwidths. This BER is still quite low, suitable for petaflop-
scale computing, but larger junctions would be needed in order to maintain
this level while taking the parametric spread of individual junctions into
account. For both the DFF and the AND gate, extrapolated BER of $10^{-25}$ or
better is maintained across an AC power range of 3.6 dB, equivalent to AC
amplitude margins of $\pm$20%.

Overall we conclude that the BER in RQL circuits is sufficiently low for
large-scale applications, even with junction critical current scaled down to
35 $\mu$A minimum in the JTLs, as predicted Herr et al. (2011). BER
performance of each gate in the library can characterized and optimized by
appropriate device sizing in the design phase, using BER simulation as the
primary tool.

## Appendix

We now describe some details of the numerical integration of the Gaussian
distribution across the operating region of the circuit. As discussed above,
mapping out the operating region is effectively to find the global minimum by
exhaustive search. If only the local minimum were wanted, the downhill simplex
method could be used. Instead the entire operating region is mapped out with
simplexes. The algorithm uses an anneal to first search exhaustively, and then
to adaptively apply higher resolution to the regions of interest.

The algorithm is as follows:

  1. 1.

Calculate all $2N$ 1 D margins and all $2^{N}$ corner margins

  2. 2.

Make the initial simplexes, each using $N-1$ margins and $1$ corner margin

  3. 3.

Update the annealing weights

  4. 4.

Find the greatest simplex based on the annealing weights

  5. 5.

Bisect it through the longest segment by finding a new point on the operating
boundary

  6. 6.

Bisect all other simplexes for which this is the longest line segment

  7. 7.

Calculate the solid angle subtended by each new simplex and update the Riemann
sum

  8. 8.

Until desired accuracy is achieved, goto (3)

Three points require further explanation: A) simplex formation and bisection,
B) the algorithm is adaptive based on an annealing schedule, and C) the solid
angle subtended by each simplex must be calculated.

###  IV.1 Bisection

The first simplexes are formed in steps (1) and (2). The “corner margins”
consist of all search vectors for which each dimension has a value of $\pm 1$.
There is one corner vector centered in each orthant. Many possibilities exist
for subsequent iterations. Experimentation indicates that keeping the aspect
ratio of each simplex small is important. This explains the conditional in
step (6) of the algorithm.

The number of simplexes grows exponentially with $N$ and with iteration
number, and becomes a limiting factor above 8-D. Integration in 7-D can create
upwards of 500,000 simplexes; in 8-D, 5,000,000 simplexes. The problem is not
storage per se, but the time spent doing unordered searches in steps (4) and
(5). Incremental sorting is needed in step (4). Step (5) would benefit from an
indexing system whereby each point had a field indicating its simplexes.
Alternately, the simplexes could be organized by orthant. in this case, the
signs of the coordinates for each point could be used as the index. The
unordered searches in the current implementation limit us to about 8 D.

###  IV.2 Anneal

Each term $\Omega_{s}\langle\mbox{Q}_{s}\rangle$ in the Riemann sum is the
product of the solid angle subtended by the simplex and the average value of Q
for the points defining the simplex, The schedule computes the annealing
weight of each simplex as $\Omega_{s}\langle\mbox{Q}_{s}\rangle^{w}$. The
schedule moves the value of $w$ from 0 to 1 incrementally. When $w=0$, the
algorithm bisects the simplex with greatest solid angle; when $w=1$, the
simplex that is most significant. In this way the algorithm starts by covering
the space uniformly, and gradually becomes more adaptive. The anneal could be
taken yet further by computing the variance among the values of the points in
each simplex, and weight the anneal accordingly. This produced unstable
results in our experimentation. However, we do compute and sum these variances
in order to estimate the error, as for error estimates in Monte Carlo
integration Press et al. (1992b).

If the anneal proceeds too quickly, the danger is that it will find some local
minima, while missing others of more significance. As stated previously,
$3^{N}$ points may be needed to cover the space. However, we have found via a
user-defined annealing parameter that completing the anneal with $2.5^{N}$
points can achieve reliable results.

###  IV.3 Solid Angles

We need the solid angle subtended by each simplex, $\Omega_{s}$. (This is the
language of three dimensions. For higher dimensions, this generalizes to the
volume subtended on the unit hypersphere.) The solid angle is normalized by
the whole, $\Omega_{N}=\pi^{N/2}/\Gamma(N/2+1)$, where $\Gamma$ is the gamma
function. The procedure for calculating the solid angle of a simplex required
some effort, as we invented our own.

First we calculate the volume, $V_{s}$, subtended by simplex $s$ on the
operating region boundary surface, by also including the point at the origin.
This volume derives from the matrix determinant. In $N$ dimensions

$V_{s}=\left|\frac{1}{N!}\,\mbox{det}(v_{1},v_{2},...,v_{N})\right|$

where $(v_{1},v_{2},...,v_{N})$ are the unit vectors associated with the
vertices of simplex $s$. The points at the center of each facet of simplex $s$
form a similar simplex. These points
$(v^{\prime}_{1},v^{\prime}_{2},...,v^{\prime}_{N})$ are calculated by
excluding the points of the simplex one-by-one and finding the center among
the remaining points:

$\displaystyle v^{\prime}_{1}$ $\displaystyle=\langle
v_{2},v_{3},...,v_{N}\rangle$ $\displaystyle v^{\prime}_{2}$
$\displaystyle=\langle v_{1},v_{3},...,v_{N}\rangle$ $\displaystyle
v^{\prime}_{N}$ $\displaystyle=\langle v_{1},v_{2},...,v_{N-1}\rangle$

Here the angle brackets denote the mean value of the vector coordinates. The
vertices of the new simplex lie inside the unit sphere. Renormalize them to
unit vectors, and calculate the volume of this new simplex, $V^{\prime}_{s}$,
again by including the point at the origin. The method centers on the
observation that the volume of the new simplex is smaller by a factor of
$V_{f}=1/(N-1)^{(N-1)}$, in the limit of small angles. Scale inversely with
$V_{f}$ to produce a new solid angle estimate

$V^{\prime}_{s}=(N-1)^{(N-1)}\left|\frac{1}{N!}\,\mbox{det}(v^{\prime}_{1},v^{\prime}_{2},...,v^{\prime}_{N})\right|$

This produces a much better estimate for the original solid angle. Finally, we
use both estimates to extrapolate to the best estimate,

$\Omega_{s}=(V^{\prime}_{s}/V_{s})^{F_{N}}V^{\prime}_{s}$

where the first term produces a correction to $V^{\prime}_{s}$. The fitting
parameter $F_{N}$ was found through experimentation.

$\displaystyle(F_{3},F_{4},...,F_{10})=(0$
$\displaystyle.0000,-0.0997,-0.1106,-0.1057,$ $\displaystyle-0$
$\displaystyle.0978,-0.0888,-0.0808,-0.0711)$

This method is effective because the correction to $V^{\prime}_{s}$ is small.
Typical accuracy was better than 1%, judged by summing the solid angles
$\Omega_{s}$ and comparing to the known value of $\Omega_{N}$.

###### Acknowledgements.

The authors acknowledge valuable discussions with Alexander Sirota, Charles
Wallace, and Henry Luo.

## References

  * Herr et al. (2011) Q. P. Herr, A. Y. Herr, O. T. Oberg, and A. G. Ioannidis, Journal of applied physics 109, 103903 (2011).
  * Holmes et al. (2013) D. S. Holmes, A. L. Ripple, and M. A. Manheimer, IEEE Transactions on Applied Superconductivity 23, 1701610 (2013).
  * Vernik et al. (2016) I. Vernik, A. Kirichenko, O. Mukhanov, and T. Ohki, IEEE Transactions on Applied Superconductivity 27, 1 (2016).
  * Herr et al. (2013) A. Y. Herr, Q. P. Herr, O. T. Oberg, O. Naaman, J. X. Przybysz, P. Borodulin, and S. B. Shauck, Journal of Applied Physics 113, 033911 (2013).
  * Ayala et al. (2021) C. L. Ayala, T. Tanaka, R. Saito, M. N. Nozoe, N. Takeuchi, and N. Yoshikawa, IEEE journal of solid-state circuits in press (2021).
  * Herr and Feldman (1996) Q. P. Herr and M. J. Feldman, Applied physics letters 69, 694 (1996).
  * Rylyakov and Likharev (1999) A. V. Rylyakov and K. K. Likharev, IEEE transactions on applied superconductivity 9, 3539 (1999).
  * Bunyk and Zinoviev (2001) P. Bunyk and D. Zinoviev, IEEE transactions on applied superconductivity 11, 529 (2001).
  * Fujiwara et al. (2005) K. Fujiwara, N. Nakajima, T. Nishigai, M. Ito, N. Yoshikawa, A. Fujimaki, H. Terai, and S. Yorozu, IEEE transactions on applied superconductivity 15, 427 (2005).
  * Wetzstein et al. (2011) O. Wetzstein, T. Ortlepp, R. Stolz, J. Kunert, H.-G. Meyer, and H. Toepfer, IEEE transactions on applied superconductivity 21, 814 (2011).
  * Tanaka et al. (2013) M. Tanaka, A. Kitayama, T. Takinami, Y. Komura, and A. Fujimaki, in _2013 IEEE 14th International Superconductive Electronics Conference (ISEC)_ (IEEE, 2013), pp. 1–3.
  * Takeuchi et al. (2017) N. Takeuchi, H. Suzuki, and N. Yoshikawa, Applied Physics Letters 110, 202601 (2017).
  * Filippov et al. (1995) T. Filippov, Y. A. Polyakov, V. Semenov, and K. Likharev, IEEE Transactions on Applied Superconductivity 5, 2240 (1995).
  * Klein and Mukherjee (1982) M. Klein and A. Mukherjee, Applied Physics Letters 40, 744 (1982).
  * Herr and Feldman (1997) Q. P. Herr and M. J. Feldman, IEEE transactions on applied superconductivity 7, 2661 (1997).
  * Satchell (1999) J. Satchell, IEEE transactions on applied superconductivity 9, 3841 (1999).
  * Kahng (2015) A. B. Kahng, in _2015 52nd ACM/EDAC/IEEE Design Automation Conference (DAC)_ (IEEE, 2015), pp. 1–6.
  * Press et al. (1992a) W. Press, S. Teukolsky, W. Vetterling, and B. Flannery, _Numerical Recipes in C 2nd edition_ (Cambridge University Press, 1992a), chap. Incomplete Gamma Function.
  * Director and Hachtel (1977) S. Director and G. Hachtel, IEEE Transactions on Circuits and Systems 24, 363 (1977).
  * Herr and Johnson (2001) Q. P. Herr and M. W. Johnson, IEEE transactions on applied superconductivity 11, 1078 (2001).
  * Braun and Harms (2018) A. L. Braun and D. C. Harms, _RQL Majority gates, And gates, and Or gates_ (2018), US Patent 10,084,454.
  * Braun (2018) A. L. Braun, _Superconducting devices with enforced directionality_ (2018), US Patent 10,153,772.
  * Whiteley (2020) S. Whiteley, _XicTools: Xic graphical editor, WRspice circuit simulator, and accessories for electronic design_ (https://github.com/wrcad/xictools, 2020).
  * Berkley et al. (2010) A. Berkley, M. Johnson, P. Bunyk, R. Harris, J. Johansson, T. Lanting, E. Ladizinsky, E. Tolkacheva, M. Amin, and G. Rose, Superconductor Science and Technology 23, 105014 (2010).
  * Harms et al. (2019) D. C. Harms, Q. P. Herr, and A. Y. Herr, _Superconducting circuits based devices and methods_ (2019), US Patent 10,411,713.
  * Likharev (1986) K. K. Likharev, _Dynamics of Josephson junctions and circuits_ (Gordon and Breach science publishers, 1986), chap. The DC Josephson Effect.
  * Harris (1979) E. Harris, IEEE Transactions on Magnetics 15, 562 (1979).
  * Averin et al. (2006) D. V. Averin, K. Rabenstein, and V. K. Semenov, Physical Review B 73, 094504 (2006).
  * Fredkin and Toffoli (1982) E. Fredkin and T. Toffoli, International Journal of theoretical physics 21, 219 (1982).
  * Herr et al. (2010) Q. P. Herr, J. E. Baumgardner, and A. Y. Herr, _Method and apparatus for ballistic single flux quantum logic_ (2010), US Patent 7,782,077.
  * Osborn and Wustmann (2020) K. D. Osborn and W. Wustmann, IEEE Transactions on Applied Superconductivity 31, 1 (2020).
  * Press et al. (1992b) W. Press, S. Teukolsky, W. Vetterling, and B. Flannery, _Numerical Recipes in C 2nd edition_ (Cambridge University Press, 1992b), chap. Simple Monte Carlo Integration.


# Self-Supervised Multi-Object Tracking
with Cross-Input Consistency

Favyen Bastani, Songtao He, Sam Madden  Favyen Bastani
MIT CSAIL
<EMAIL_ADDRESS>
&Songtao He
MIT CSAIL
<EMAIL_ADDRESS>
&Sam Madden
MIT CSAIL
<EMAIL_ADDRESS>

###### Abstract

In this paper, we propose a self-supervised learning procedure for training a
robust multi-object tracking (MOT) model given only unlabeled video. While
several self-supervisory learning signals have been proposed in prior work on
single-object tracking, such as color propagation and cycle-consistency, these
signals cannot be directly applied for training RNN models, which are needed
to achieve accurate MOT: they yield degenerate models that, for instance,
always match new detections to tracks with the closest initial detections. We
propose a novel self-supervisory signal that we call cross-input consistency:
we construct two distinct inputs for the same sequence of video, by hiding
different information about the sequence in each input. We then compute tracks
in that sequence by applying an RNN model independently on each input, and
train the model to produce consistent tracks across the two inputs. We
evaluate our unsupervised method on MOT17 and KITTI — remarkably, we find
that, despite training only on unlabeled video, our unsupervised approach
_outperforms_ four supervised methods published in the last 1–2 years,
including Tracktor++ [1], FAMNet [5], GSM [18], and mmMOT [29].

##  1 Introduction

Multi-object trackers identify all instances of a particular object type in
video, and track each instance through the segment of video in which it is
visible in the camera frame. Annotating training data for multi-object
tracking is tedious and costly; for example, annotation of pedestrian tracks
in just six minutes of video in the training set of the MOT15 Challenge [14]
requires an estimated 22 hours [20] of human labeling time using LabelMe [28].
While unsupervised, heuristic detect-to-track methods [2, 4] have been
proposed that group detections into tracks by estimating motion using a
combination of spatial and visual cues, these methods suffer low-accuracy in
scenarios with frequent occlusion where heuristics are insufficient.

Recent work has proposed applying self-supervised learning for training
_single_ -object tracking models on unlabeled video [24, 25]. These approaches
train a model to propagate instance labels from a reference frame through the
rest of a video sequence. In contrast to work on self-supervised
representation learning from video, these fully unsupervised approaches do not
require fine-tuning to apply the model for single-object tracking.

However, a significant limitation in prior work is that the model
independently compares pairs of frames at a time. In multi-object tracking, a
key challenge is robustly re-localizing tracks across potentially long
occlusions, especially when an object instance is occluded by other instances
of the same object type. Pairwise frame comparisons are thus insufficient for
high-accuracy multi-object tracking; instead, learning recurrent features that
encode the history of a track is crucial for enabling robust re-localization.
However, extending prior work to learn RNN parameters is challenging. For
example, Wang et al. [25] propose training using forward-backward consistency:
from a patch in an initial frame, after tracking forwards through video and
then backwards to return to the initial frame, the final patch should align
with the original patch. Training an RNN in this way would be ineffective as
the RNN could simply memorize the features of the original patch.

To address this challenge, we propose a novel self-supervised learning method,
_cross-input consistency_. We first compute object detections in each frame of
unlabeled video (like unsupervised, heuristic detect-to-track methods, we
assume that a robust detector is available). Then, we derive a learning signal
from the unlabeled video by sampling a short sequence of contiguous frames
from the video, constructing two input variations of that sequence that each
hide different information about objects detected in the sequence, and
training the tracker to produce consistent tracking outputs when applied
independently on each of the two inputs. We propose two alternative input-
hiding schemes for computing the input variations: visual-spatial hiding and
occlusion-based hiding. Visual-spatial hiding applies the tracker once when
only observing spatial inputs (bounding box coordinates in the video frame),
and once when only observing visual inputs (pixel values inside detection
boxes). Occlusion-based hiding eliminates information about object detections
in random intermediate subsequences of frames to simulate occlusion incidents;
thus, it constructs two inputs by eliminating different subsequences of
detections in each input. After sampling a sequence of video and computing the
two input variations under the chosen input-hiding scheme, we apply the
tracker model independently on each input, and back-propagate a learning
signal that measures the consistency between tracks computed across the two
inputs. To attain high consistency, the model must accurately group detections
that correspond to the same object: if the model were to instead arbitrarily
group detections into tracks, then variations in the inputs would cause the
tracker to produce inconsistent outputs.

To implement cross-input consistency, we adapt a now standard RNN model and
tracker architecture from prior work [12]: the tracker processes each frame in
sequence by matching detections in the current frame with tracks computed up
to the previous frame. In prior work, this model is trained under a supervised
procedure: they sample a video sequence $\langle I_{0},\ldots,I_{n}\rangle$
and a track $t$ in that sequence, and apply the tracker on $t$ over the
sequence. On each frame $I_{j}$, the RNN outputs a probability distribution
indicating the likelihood that the prefix of a track $t$ up to $I_{j}$ matches
with each detection in $I_{j}$. Prior work back-propagates the label (i.e.,
the correct detection of $t$ in $I_{j}$) under cross entropy loss.

In contrast, under our method, on each training iteration, we propose to
sample a sequence $\langle I_{0},\ldots,I_{n}\rangle$ from a corpus of
unlabeled video, and apply the RNN model to compute a transition matrix that
specifies the probability that each detection in $I_{0}$ (rows) matches with
each detection in $I_{n}$ (columns). We select the sequence length $n$ so that
most objects in $I_{0}$ are still visible in $I_{n}$. Then, when applying the
tracker on two input variations extracted from the sequence, we obtain two
transition matrices (one for each input). We compute the dot-product
similarity to measure the consistency between these matrices, and back-
propagate the negative similarity as a loss function.

We evaluate our approach on the MOT17 and KITTI benchmarks against 9
baselines, including both unsupervised and supervised methods. We train our
tracker model using cross-input consistency over a corpus of unlabeled video,
which can be cheaply obtained. Like other unsupervised methods, we use an
object detector trained on image-level bounding box annotations in COCO [17],
but do not use any expensive video-level annotations. We find that, on MOT17,
our approach improves both IDF1 and MOTA accuracy over the unsupervised
baselines by 14% to 18%. Moreover, remarkably, our fully unsupervised approach
_outperforms_ five of the seven supervised methods we compared, even though
these methods train on expensive video-level bounding box and track
annotations.

Our code is available at https://favyen.com/uns20/.

Figure 1: Overview of cross-input consistency. An input-hiding scheme produces
two inputs, A and B, from one video sequence; these inputs contain identical
information about objects detected in the first and last frames of the
sequence, but vary in intermediate frames. We apply the tracker model on each
input to derive two transition matrices that match detections between the
first and last frames to represent tracker outputs. We then back-propagate a
similarity score between the matrices that encourages the model to produce
consistent outputs across both inputs.

##  2 Related Work

Self-supervised learning over video has been studied extensively in many
contexts. Most work focuses on learning representations of video that can be
applied through fine-tuning for tasks such as activity recognition, image
classification, and object detection [6, 7, 9, 15, 23, 26]. More closely
related to our work, several recent approaches have proposed leveraging widely
available unlabeled video to directly train _single_ -object tracking models,
without needing fine-tuning [13, 16]. Vondrick et al. [24] train a model to
colorize gray-scale video by propagating colors from a colored reference
frame. The model is then applied to track objects at inference time by
propagating instance IDs instead of colors. Wang et al. [25] train a model to
capture correspondence by applying a cycle-consistent loss: from a patch in an
initial frame, after tracking forwards through video and then backwards to
return to the initial frame, the final patch should align with the original
patch. As we discussed in Section 1, self-supervisory signals used in prior
work such as color propagation and cycle-consistency are not effective for
training RNN models, which are needed to achieve accurate MOT.

Our work is also related to unsupervised, heuristic detect-to-track multi-
object tracking methods such as SORT [2] and V-IOU [4]. These methods group
detections across different frames using a combination of heuristic spatial
cues (e.g., Kalman filter over bounding box coordinates) and visual cues
(e.g., optical flow) to track objects. Like our approach, these methods assume
that a robust detector is available; however, because they rely on heuristics
to group detections into tracks, they suffer low-accuracy in scenarios with
frequent occlusion.

Multi-object tracking has been studied extensively in supervised settings,
where methods are trained on video-level bounding box and track annotations
[1, 5, 8, 12, 18, 30]. However, such annotations are expensive to hand-label,
and so these methods are costly to extend to new types of video.

Other work explores using unsupervised and self-supervised learning to further
improve the performance of fully supervised methods. SimpleReID [11] proposes
improving the performance of one supervised method, CenterTrack [30], by
training a re-identification model through unsupervised learning. However,
while the model can in principle be trained only on image-level annotations
through hallucinated motion techniques, their SimpleReID+CenterTrack tracking
method depends on expensive video-level annotations to attain high-accuracy.
In contrast, our method achieves competitive results without any video-level
supervision.

##  3 Cross-Input Consistency

Figure 2: Tracker model architecture. The model scores the likelihood that
each detection in the current frame matches with each track.

In our novel cross-input consistency method, we derive an learning signal for
training an RNN tracker model through a three-step process. We assume that a
corpus of unlabeled video is available, along with an object detector for the
object category of interest. During pre-processing, we apply the detector on
each frame of unlabeled video to compute object detections. Then, during
training, we first repeatedly randomly sample a sequence of contiguous frames
from the video, $\langle I_{0},\ldots,I_{n}\rangle$, where each $I_{k}$ is a
video frame. Let $D_{k}$ by the detections automatically computed in $I_{k}$
by the detector, and let $d^{k}_{i}=(im,x,y,w,h)$ be a detection in $D_{k}$,
where $(x,y,w,h)$ are the 4D spatial coordinates (center point and lengths) of
the detection bounding box, and $im$ is the window of $I_{k}$ corresponding to
that box. We apply an input-hiding scheme to select two input variations
$A(D),B(D)$ for the video segment, where each variation is a modified sequence
of detections in the frames, $A(D)=\langle
D^{A}_{0},\ldots,D^{A}_{n}\rangle,B(D)=\langle
D^{B}_{0},\ldots,D^{B}_{n}\rangle$. For example, some detections may be
removed entirely, while others may be partially hidden. Second, we apply the
tracker model independently on each input variation to derive two
probabilistic tracking outputs (one per input), represented as transition
matrices. Third, we compare the transition matrices with dot-product
similarity to update the RNN parameters.

Figure 1 summarizes our approach.

Below, we first introduce the model architecture that we adapt from prior work
in Section 3.1. We then detail our novel training procedure, including the
computation of the transition matrices and dot-product loss, in Section 3.2.
Finally, we propose two input-hiding schemes for selecting the input
variations required by our approach in Section 4.

###  3.1 Background: Tracker Model

We adopt a tracker model that is similar to prior work [12]. We summarize the
architecture in Figure 2. Given a video sequence $\langle
I_{0},\ldots,I_{n}\rangle$, and sets of detections
$D_{k}=\\{d^{k}_{1},\ldots,d^{k}_{m_{k}}\\}$ detected in each frame $I_{k}$,
to initialize the tracking process, we create a length-1 track $t_{i}=\langle
d^{0}_{i}\rangle$ for each detection $d^{0}_{i}$ in the first video frame
$I_{0}$. When processing subsequent frames, we will match the new detections
with existing tracks, extending existing tracks if there is a match and
initializing new tracks otherwise. Specifically, on each subsequent frame
$I_{k}$, the model outputs a probability $p_{i,j}$ that each track $t_{i}$
corresponds to each detection $d^{k}_{j}\in D_{k}$. At inference time, we
formulate the problem of matching tracks with detections in $I_{k}$ as a
bipartite matching problem, where the cost of matching $t_{i}$ with
$d^{k}_{j}$ is $1-p_{i,j}$. We solve this problem and compute a minimum-cost
matching using the Hungarian algorithm; for each pair $(t_{i},d^{k}_{j})$ in
the matching, we append $d^{k}_{j}$ to $t_{i}$. For each detection in $I_{k}$
that no track matches to, we create a new track for that detection.

The model consists of a CNN, RNN, and matcher network. Together, these
components score the likelihood that the $i$th track, $t_{i}=\langle
d_{1},\ldots,d_{m}\rangle$, matches with the $j$th detection in $I_{k}$,
$d^{k}_{j}$. We first apply the CNN to derive detection-level features. Given
a detection $d=(im,x,y,w,h)$, the CNN inputs $im$ resized to $64\times 64$,
and consists of 6 strided convolutional layers, with ReLU activation in the
first 5 layers and linear activation in the last layer. It outputs a
64-vector, which we concatenate with the 4D spatial coordinates to derive a
68-vector detection representation $f(d)$. Then, we compute track-level
features $f(t_{i})$ by applying the RNN (an LSTM with 64 hidden states) over
the sequence of detection-level features of detections in the track, $\langle
f(d_{1}),\ldots,f(d_{m})\rangle$. We use the output of the RNN on the last
timestep as the track-level features $f(t_{i})$. Finally, we apply a matching
network to score the likelihood that $t_{i}$ matches $d^{k}_{j}$. The matching
network inputs the concatenation of $f(t_{i})$ and $f(d^{k}_{j})$, applies
four fully-connected layers, and outputs a match score.

###  3.2 Training Procedure

We develop a novel self-supervised learning method for training the model
parameters on unlabeled video. During training, we repeatedly sample sequences
of video $\langle I_{0},\ldots,I_{n}\rangle$. We apply one of two input-hiding
schemes, which we will detail in the following section, to extract two
distinct input variations $A(D)$ and $B(D)$ from a sampled video sequence,
where each input is a sequence of detections. We then apply the tracker
independently on $A(D)$ and $B(D)$ to derive two tracking outputs for the same
video sequence. In cross-input consistency, we train the model by enforcing
similarity between these two outputs.

To represent tracker outputs, we compute an $|D_{0}|\times|D_{n}|+1$
transition matrix $M^{(0,n)}$, where $M^{(0,n)}_{i,j},j<|D_{n}|$ is the
probability that the track $t_{i}$ matches $d^{n}_{j}$. We use the last column
to represent tracks that are no longer visible in $I_{n}$, i.e.,
$M^{(0,n)}_{i,|D_{n}|}$ is the probability that the track $t_{i}$ has exited
the camera frame. When applying the model over video sequences during
training, we update tracks with new detections based on the scores output by
the model on intermediate frames, but do not create additional tracks on
frames after $I_{0}$; thus, each track $t_{i}$ corresponds directly to a
detection $d^{0}_{i}$ in $I_{0}$ (i.e., $t_{i}=\langle
d^{0}_{i},\ldots\rangle$). Thus, we can also think of $M^{(0,n)}$ as the
probability that a detection in the first frame $d^{0}_{i}$ matches a
detection in the last frame $d^{n}_{j}$.

Applying the tracker on both input variations yields two transition matrices
$A^{(0,n)}$ and $B^{(0,n)}$ that match objects detected in $I_{0}$ with those
in $I_{n}$. We train the model (CNN, RNN, and matching network) to maximize
the dot-product similarity between these matrices. In addition to pushing the
model to produce consistent outputs across both inputs, we also design our
training method so that the model cannot attain a high similarity score by,
for example, saying that all objects visible in $I_{0}$ are no longer visible
in $I_{n}$.

In our method, it is important that the training sequence length $n$ be chosen
so that, in most sequences, most (but not all) objects in $I_{0}$ are still
visible in $I_{n}$, but that objects nevertheless move non-trivially during
the sequence (so that the tracking task is not too easy). In general, we find
that setting $n$ to one-half of the average time that objects linger in the
camera frame works well; this value can be quickly estimated by hand-labeling
the duration of a few (e.g., 10-20) objects randomly sampled from the video.

Below, we detail our method to compute transition matrices, and discuss dot-
product similarity loss.

Transition Matrix. We propose computing a transition matrix $M^{(0,k)}$ on
each frame $I_{k}$ to represent the tracker outputs, where $M^{(0,k)}_{i,j}$
is the probability that the track $t_{i}$ matches the detection $d^{k}_{j}$.
On intermediate frames, we apply the Hungarian method on $M^{(0,k)}$ to match
detections in $D_{k}$ with tracks, updating each track with the matched
detection (if any). On the last frame $I_{n}$, we use the $M^{(0,n)}$ matrix
produced under different inputs (denoted $A^{(0,n)}$ and $B^{(0,n)}$) to
compute and back-propagate a consistency score. Because we do not create new
tracks after $I_{0}$ during training, $M^{(0,n)}_{i,j}$ is the likelihood that
$d^{0}_{i}$ and $d^{n}_{j}$ match (since $t_{i}$ begins with $d^{0}_{i}$).

We first construct a score matrix $S^{(0,k)}$, by computing $S^{(0,k)}_{i,j}$
as the score (any real number) output by the tracker model given the track
$t_{i}$ and detection $d^{k}_{j}$. We then transform the score matrix into a
probability matrix to derive $M^{(0,k)}$. We could simply compute $M^{(0,k)}$
by taking softmax along rows in $S^{(0,k)}$. However, computing the transition
matrix in this way would allow the tracker to cheat and maximize similarity
between $A^{(0,n)}$ and $B^{(0,n)}$ by simply matching all detections in
$I_{0}$ to a single detection $d^{n}_{j}\in D_{n}$. Indeed, we find that in
practice this yields degenerate models.

Thus, instead, we compute $M^{(0,k),\text{row}}$ and $M^{(0,k),\text{col}}$ by
applying softmax along rows and columns, respectively, and compute
$M^{(0,k)}=\min(M^{(0,k),\text{row}},M^{(0,k),\text{col}})$:

$\displaystyle
M^{\text{row}}_{i,j}=\frac{\text{exp}(S_{i,j})}{\sum_{k}\text{exp}(S_{i,k})}$
$\displaystyle\qquad
M^{\text{col}}_{i,j}=\frac{\text{exp}(S_{i,j})}{\sum_{k}\text{exp}(S_{k,j})}$
$\displaystyle\qquad M_{i,j}=$
$\displaystyle\min(M^{\text{row}}_{i,j},M^{\text{col}}_{i,j})$ (1)

This produces a transition matrix $M^{(0,k)}$ that is almost doubly
stochastic: rows and columns sum to at most 1, but not necessarily exactly 1.
The operation ensures that the model must match each detection in $I_{0}$ to
unique detections in $I_{n}$ to maximize the consistency score between
$A^{(0,n)}$ and $B^{(0,n)}$: if two detections in $I_{0}$ are matched to the
same detection in $I_{n}$, then the columnar softmax would reduce those
probabilities in the corresponding matrix to at most 0.5, thereby reducing any
dot-products involving those rows.

Dot-Product Similarity. We train the RNN tracker by computing two transition
matrices $A^{(0,n)}$ and $B^{(0,n)}$ over different input variations, and then
back-propagating a loss that measures the inconsistency between the matrices.
In particular, we use the dot-product to measure the similarity of
corresponding rows in the matrices. We define the loss as:

$L=-\sum_{i}\log\sum_{j}A^{(0,n)}_{i,j}B^{(0,n)}_{i,j}$

Here, $L$ is computed by taking the logarithm of the dot product of
corresponding rows in $A^{(0,n)}$ and $B^{(0,n)}$, averaged across rows. Note
that this is equivalent to the cross-entropy loss between the diagonal matrix
and the matrix product of $A^{(0,n)}$ and the transpose of $B^{(0,n)}$.

This loss function has several desirable properties. First, the dot-product is
maximized when the matrices computed based on different inputs are most
similar. This pushes the matching model to learn reasonable visual and spatial
tracking constraints, because arbitrarily matching tracks to detections will
lead to dissimilarity. Second, the dot-product pushes each matrix to be almost
doubly stochastic rather than leaving some rows and columns summing to much
less than 1. The model can only produce doubly stochastic $A^{(0,n)}$ and
$B^{(0,n)}$ matrices by finding unique detections in $I_{n}$ for each
detection in $I_{0}$.

Spatial Mask. In some cases, training as described above may converge at a
local minimum where the model outputs uniform probabilities for all entries in
$M$. To mitigate this issue, we add a spatial constraint to the loss that
penalizes the tracker when it matches detections that are highly improbable to
correspond to the same object based on bounding box positions. We first
compute a mask matrix $C^{(0,n)}$ so that $C^{(0,n)}_{i,j}=0$ if it is
“improbable” that $d^{0}_{i}$ matches $d^{n}_{j}$, and $C^{(0,n)}_{i,j}=1$
otherwise. Then, we compute $L$ as:

$L=-\sum_{i}\log\sum_{j}A^{(0,n)}_{i,j}B^{(0,n)}_{i,j}C^{(0,n)}_{i,j}$

We determine whether matches in $C$ are improbable by applying a simple
floodfill-like algorithm that propagates sets of labels from the first frame
$I_{0}$ to the last frame $I_{n}$. If the label from a detection $d^{0}_{i}$
in $I_{0}$ does not propagate to a detection $d^{k}_{j}$, then it implies
there is no sequence of intermediate detections that could form a track
between $d^{0}_{i}$ and $d^{k}_{j}$. In $I_{0}$, we label each detection
$d^{0}_{i}$ with a set containing only that detection, i.e.,
$\\{d^{0}_{i}\\}$. In $I_{k}$, we label each detection $d^{k}_{j}$ with the
union of sets of labels of detections $d^{k-l}_{i}$ in preceding frames
$I_{k-l}$ ($1\leq l\leq 10$) such that the bounding boxes of $d^{k}_{j}$ and
$d^{k-l}_{i}$ intersect. Note that we consider several preceding frames since
the detector may occasionally fail to localize an object in an intermediate
frame. Then, $C^{(0,n)}_{i,j}=1$ only if the label set for $d^{n}_{j}$
includes $d^{0}_{i}$.

Artificial Detections. To improve the model’s robustness in learning visual
features, we artificially construct additional detections in $I_{n}$ by
pairing the spatial coordinates of detections in $I_{n}$ with object images
selected randomly from frames in the underlying video data that are temporally
far from $\langle I_{0},\ldots,I_{n}\rangle$. Thus, these artificial
detections added to $D_{n}$ have correct spatial coordinates, but include
visual cues that do not correspond to any object in $I_{0}$, and so the
tracker model must learn to leverage visual cues so that it does not assign
high probabilities in $M^{(}0,n)$ to artificial detections.

We exclude artificial detections in the mask $C$. Then, to perform well under
dot-product similarity, the model must learn to leverage visual features to
distinguish the correct detections in $I_{n}$ from artificially constructed
ones — a tracker that only considers spatial features would assign half of its
probability mass along each row to artificial detections, and thus would be
penalized by the loss.

##  4 Input-Hiding Schemes

Figure 3: Visual-spatial hiding. One input includes only visual information
about the detections, while the other includes only spatial bounding box
coordinates. Figure 4: Occlusion-based hiding produces input variations with
different subsequences of occluded frames where all detections are hidden from
the tracker. It also independently applies the tracker before and after a
hand-off frame ($I_{4}$ and $I_{2}$), and merges the outputs through the
matrix product.

In this section, we detail two alternative input-hiding schemes for selecting
the two input variations, denoted $A(D)=\langle
D^{A}_{0},\ldots,D^{A}_{n}\rangle$ and $B(D)=\langle
D^{B}_{0},\ldots,D^{B}_{n}\rangle$. Recall that $D$ is the original set of all
objects detected in a video sequence $\langle I_{0},\ldots,I_{n}\rangle$.
Although we only introduce two schemes, our cross-input consistency framework
is general-purpose, and there may be other input-hiding schemes that offer
comparable or better performance.

###  4.1 Visual-Spatial Hiding

Under visual-spatial hiding, we apply one tracker instance that observes only
visual features and one tracker instance that observes only spatial features:
in $A(D)$, we set $x=0,y=0,w=0,h=0$ for all detections (hide all spatial
information), and in $B(D)$, we set $im=0$ (hide the image content).

Training with cross-input consistency forces the model to produce similar
outputs between the visual and spatial inputs. We find that, in practice, the
model naturally learns to robustly track objects, because doing anything else
would not lead to high consistency. For example, when given visual features,
the model must learn to match detections based on visual similarity in order
to be consistent with matching based on spatial proximity. Similarly, when
given spatial features, the model must learn to estimate motion across
occlusion, since the visual-only instance would not have difficulty re-
localizing a visually distinctive object following frames where it was
occluded.

A key issue with visual-spatial hiding is that the visual-only instance can
estimate the change in spatial coordinates of an object between two frames by
comparing the background of the detection bounding boxes of that object across
the frames, similar to optical flow. This reduces performance because the
visual-only instance then learns only to process the background rather than
learn a robust embedding for contrasting distinct objects. To mitigate the
issue, we make adjustments to the training and inference procedures.

Training. We prevent the visual-only instance from focusing on background
features when matching detections in $I_{n}$ with those in $I_{0}$ by
encumbering its ability to aggregate estimates of changes in spatial
coordinates across sequences of consecutive frames: although processing the
background is sufficient to compute spatial movement between detections that
are in close proximity (e.g., detections of the same object between
consecutive frames), this strategy fails for detections that share no overlap.
Thus, for sufficiently large $n$, where objects move substantially during the
sampled video sequence, background processing is only an issue because the
tracker can add up changes that it computes between each pair of consecutive
frames.

In particular, we eliminate the recurrent unit for the visual-only instance:
its matching network inputs visual features for detections in $I_{0}$ and for
detections in $I_{n}$, and scores each pair of detections in $A^{(0,n)}$
without observing intermediate frames. On the other hand, we make no changes
to the spatial-only instance: it computes $B^{(0,n)}$ by processing 4D spatial
coordinates for each detection in every frame in the sequence, and employs
both the recurrent unit and the matching network. Figure 3 illustrates the
training procedure.

Inference. The separation of visual and spatial inputs, and the specialized
training procedure that we employ, imposes two challenges during inference.
First, because the visual-only and spatial-only instances observe very
different inputs, we cannot expect the model to perform well when we provide
both inputs—in effect, we have trained two separate models. Second, since we
eliminated recurrent features for the visual-only instance during training,
the visual-only instance is essentially a re-identification model, and we must
decide how to apply it during inference to take advantage of multiple prior
observations of a track in previous frames.

To address the first challenge, during inference, for an input video sequence
$\langle I_{0},\ldots,I_{k}\rangle$, we independently compute the visual-only
tracker output $A^{(0,k)}$ and the spatial-only tracker output $B^{(0,k)}$. We
then compute $M^{(0,k)}$ as the minimum of $A^{(0,k)}$ and $B^{(0,k)}$, and
use $M^{(0,k)}$ to update tracks before processing the next frame. Taking the
minimum for a matching between track $t_{i}$ and detection $d^{k}_{j}$ ensures
that the final transition probability reflects whichever of the visual
features or spatial features that make $d^{k}_{j}$ less likely to match with
$t_{i}$. This is desirable—for example, two red sedans visible in the same
segment of video will have high visual similarity, and we may have to leverage
spatial features to distinguish them.

The second challenge is that the visual-only tracker lacks recurrent features,
and thus is only able to compare pairs of frames. To address this, when using
the visual-only tracker, for each track-detection pair $(t_{i},d^{k}_{j})$, we
compute 5 scores by applying the model on $d^{k}_{j}$ and 5 randomly selected
images associated with the track $t_{i}$ in previous frames. We then average
these scores to derive $A^{(0,k)}_{i,j}$. This enables the model to use
context from multiple preceding frames when localizing an object in a new
frame.

###  4.2 Occlusion-based Hiding

We also experimented with an occlusion-based hiding scheme. Since we found
that visual-spatial hiding performs better, we introduce occlusion-based
hiding only at a high level here, but include details in the supplementary
material.

Occlusion-based hiding produces the variations $A(D)$ and $B(D)$ by simulating
random occlusion incidents where all detections in occluded frames are
eliminated from the input, i.e., if $I_{k}$ is occluded for $A(D)$, then
$D^{A}_{k}$ is empty. We only occlude intermediate frames (i.e., a frame
$I_{k}$ is only considered for occlusion if $0<k<n$) so that the transition
matrices still compare detections in $I_{0}$ with those in $I_{n}$. When
processing an occluded $I_{k}$, the tracker is forced to match all tracks to
the absent column in that frame, and re-localize the tracks after the
occlusion. In occlusion-based hiding, we also incorporate an RNN hand-off
method that cuts off the propagation of RNN features from $I_{0}$ to $I_{n}$
by employing two separate RNN executions: for some handoff index $1<h<n$, we
apply the model from $I_{0}$ to $I_{h}$, and separately apply the model from
$I_{h}$ to $I_{n}$, and combine the transition matrices by taking their
product. We summarize the scheme in Figure 4.

##  5 Evaluation

Method | IDF1 | MOTA
---|---|---
Occlusion (ours) | 52.4 | 56.7
Visual-Spatial (ours) | 57.3 | 60.2
Spatial-Only (ours) | 56.5 | 57.8

Table 1: Ablation study on the MOT17 training set.

| Method | IDF1 | MOTA | MT | ML | FP | FN | Idsw | Frag
---|---|---|---|---|---|---|---|---|---
Unsupervised | Visual-Spatial (ours) | 58.3 | 56.8 | 538 | 880 | 12K | 231K | 1K | 2K
Methods | SORT [2] | 39.8 | 43.1 | 295 | 997 | 28K | 288K | 5K | 7K
| IOU [3] | 39.4 | 45.5 | 369 | 953 | 20K | 282K | 6K | 7K
| Tracktor++ [1] | 52.3 | 53.5 | 459 | 861 | 12K | 248K | 2K | 5K
| MHT-BLSTM [12] | 51.9 | 47.5 | 429 | 981 | 26K | 268K | 2K | 3K
Supervised | FAMNet [5] | 48.7 | 52.0 | 450 | 787 | 14K | 254K | 3K | 5K
Methods | LSST [8] | 62.3 | 54.7 | 480 | 944 | 26K | 228K | 1K | 4K
| GSM [18] | 57.8 | 56.4 | 523 | 813 | 14K | 230K | 1K | 3K
| CenterTrack [30] | 59.6 | 61.5 | 621 | 752 | 14K | 201K | 3K | 5K

Table 2: Performance on the MOT17 test set. We compare methods in terms of
IDF1 and MOTA, but include other non-comprehensive metrics from MOT17 as well
for completeness.

Method | HOTA | DetA | AssA | DetRe | DetPr | AssRe | AssPr | LocA
---|---|---|---|---|---|---|---|---
Visual-Spatial (ours) | 62.5 | 61.1 | 65.3 | 67.7 | 73.8 | 69.1 | 83.1 | 80.3
SORT [2] | 42.5 | 44.0 | 41.3 | 47.3 | 73.9 | 42.8 | 83.0 | 80.8
FAMNet [5] | 52.6 | 61.0 | 45.5 | 64.4 | 78.7 | 48.7 | 77.4 | 81.5
mmMOT [29] | 62.1 | 72.3 | 54.0 | 76.2 | 84.9 | 59.0 | 82.4 | 86.6
CenterTrack [30] | 73.0 | 75.6 | 71.2 | 80.1 | 84.6 | 73.8 | 89.0 | 86.5

Table 3: Performance on the KITTI test set (tracking cars). We show
unsupervised methods, including our approach, at the top, and methods that
require video-level annotations at the bottom. We use HOTA to compare methods,
but include other non-comprehensive metrics from KITTI for completeness.

We compare our method and nine baselines on the MOT17 [21] and KITTI [10]
benchmarks.

Baselines. We compare with two unsupervised methods (SORT [2] and V-IOU [4])
and seven fully supervised methods (Tracktor++ [1], MHT-BLSTM [12], FAMNet
[5], LSST [8], GSM [18], mmMOT [29], and CenterTrack [30]). Like our approach,
SORT and V-IOU require an object detector, but do not train on any video-level
bounding box and track annotations in the MOT17 and KITTI training sets. The
fully supervised methods train on video-level annotations; Tracktor++
incorporates a core component that uses only the detector regression network,
but requires video-level annotations for training a re-identification network.
Results for 8 baselines are available on MOT17, and results for 4 baselines
are available on KITTI.

Dataset. MOT17 [21] consists of 14 video sequences of pedestrians in a wide
range of contexts, including a moving camera inside a shopping mall and a
fixed, elevated view of an outdoor plaza. The dataset is split into 7 training
sequences and 7 test sequences; each split includes approximately 11 minutes
of video. KITTI [10] consists of 48 video sequences captured from vehicle-
mounted cameras, split into 20 for training and 28 for testing, and the
objective is to track cars.

Training. The supervised baselines train on video-level bounding box and track
annotations provided by MOT17 and KITTI. In contrast, our method trains only
on a corpus of unlabeled video. Because video-level annotations are expensive
to label, our method requires substantially less annotation time, and thus
greatly reduces the effort needed to apply multi-object tracking on new
datasets.

For MOT17, we collect unlabeled video from two sources: we use five hours of
video from seven YouTube walking tours, and all train and test sequences from
the PathTrack dataset [20] (we do not use the PathTrack ground truth
annotations). For KITTI, we use both the 46 minutes of video in the KITTI
dataset together with 7 hours of video from Berkeley DeepDrive [27]. We train
our tracker model on an NVIDIA Tesla V100 GPU; training time varies between 4
and 24 hours depending on the input-hiding scheme. During training, we
randomly select sequence lengths $n$ between 4 and 16 frames, and apply
stochastic gradient descent one sequence at a time. We apply the Adam
optimizer with learning rate 0.0001, decaying to 0.00001 after plateau.

In contrast to MOT17, KITTI does not provide object detections for use by
tracking methods. We extract detections from video using a YOLOv5 model
trained on COCO. On MOT17, we pre-process the provided Deformable Parts Model,
Faster R-CNN, and Scale-Dependent Pooling detections with classification and
regression following the pre-processing method in Tracktor++ [1].

Metrics. We use Multi-Object Tracking Accuracy (MOTA) [21] and ID F1 Score
(IDF1) [22] on MOT17, and Higher Order Tracking Accuracy (HOTA) [19] for
KITTI. Broadly, these comprehensive metrics measure the accuracy of inferred
tracks against ground truth tracks, and penalize both when an inferred track
contains a detection that doesn’t match to some ground truth detection (or
vice versa), and when a ground truth track is split into two or more inferred
tracks (or vice versa). MOT17 and KITTI employ several other non-comprehensive
metrics, many of which are used to compute MOTA, IDF1, and HOTA; we report
these for completeness.

Ablation Study. We first compare occlusion-based hiding and visual-spatial
hiding on the MOT17 training set in Table 3. Visual-spatial hiding yields
higher performance on both MOTA and IDF1 — because objects are often visible
in the video for only a short duration, when training under occlusion-based
hiding, the model is unable to learn to re-localize objects over simulated
occlusions since the simulated occlusion must then also be short. Under
Spatial-Only, we show results for visual-spatial hiding when inputting only
the spatial coordinates of detections during inference (no image features).

Quantitative Results. Table 3 shows results on the MOT17 test set111These
results are taken from https://motchallenge.net/results/MOT17/, where our
method is denoted UNS20regress. Baselines are denoted SORT17, IOU17,
Tracktor++, MHT_bLSTM, FAMNet, LSST17, GSM_Tracktor, and CTTrackPub., and
Table 3 shows results on the KITTI test set222These results are taken from
http://www.cvlibs.net/datasets/kitti/eval_tracking.php.. Metrics are
automatically computed by the challenge websites. Per the challenge policies,
we only submit the best method, and thus show Visual-Spatial performance.

On MOT17, our approach substantially outperforms both of the unsupervised
baselines. Moreover, despite training only on unlabeled video, our method
_outperforms_ Tracktor++ [1], MHT-BLSTM [12], FAMNet [5], and GSM [18], even
though these baselines (all of which except MHT-BLSTM were published in the
last 1–2 years) are supervised methods that train on expensive video-level
annotations in the MOT17 training set. Our approach is also competitive with
LSST [8], yielding higher MOTA but lower IDF1. Nevertheless, CenterTrack [30]
yields slightly higher accuracy on both metrics.

Similarly, on KITTI, our approach outperforms SORT [2], FAMNet [5], and mmMOT
[29], but yields lower performance than CenterTrack [30].

Figure 5: Output of Visual-Spatial on a portion of an MOT17 sequence. Our
method tracks objects through several instances of occlusion.

Qualitative Results. We show qualitative results in Figure 5.

Additional Experiments. In the supplementary material, we report results for
five additional experiments, where we compare MOTA on the MOT17 training set
when various experimental parameters are changed, including detector accuracy,
unlabeled video corpus size, and the training example sequence length $n$.

##  6 Conclusion

In this paper, we have shown that a robust, fully unsupervised multi-object
tracker can be trained through a novel self-supervisory learning signal,
cross-input consistency, that enforces consistency in the tracking outputs
across different input variations of one video sequence. Despite training only
on unlabeled video, our approach outperforms four supervised trackers
published in the last 1–2 years (Tracktor++ [1], FAMNet [5], GSM [18], and
mmMOT [29]), which train on expensive video-level bounding box and track
annotations.

Social Impact. By enabling a robust multi-object tracker to be trained given
only unlabeled video, our work promises to greatly reduce the effort for users
to apply multi-object tracking on new datasets without sacrificing accuracy.
Thus, we believe that our novel self-supervised MOT method can open up new
video analytics tasks that were previously too costly. This impact may be
positive or negative depending on the nature of these tasks — however, in
general, we believe that tasks with greater potential for negative impact such
as surveillance and pedestrian tracking would not benefit from the reduction
in annotation cost associated with our method.

Funding Transparency Statement. This research was supported in part by the
Qatar Computing Research Institute (QCRI).

## References

  * [1] Philipp Bergmann, Tim Meinhardt, and Laura Leal-Taixe.  Tracking without bells and whistles.  In IEEE International Conference on Computer Vision (ICCV), 2019\.
  * [2] Alex Bewley, Zongyuan Ge, Lionel Ott, Fabio Ramos, and Ben Upcroft.  Simple Online and Realtime Tracking.  In IEEE International Conference on Image Processing (ICIP), 2016\.
  * [3] Erik Bochinski, Volker Eiselein, and Thomas Sikora.  High-Speed Tracking-by-Detection Without Using Image Information.  In IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS), 2017.
  * [4] Erik Bochinski, Tobias Senst, and Thomas Sikora.  Extending IOU Based Multi-Object Tracking by Visual Information.  In IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS), 2018.
  * [5] Peng Chu and Haibin Ling.  FAMNet: Joint Learning of Feature, Affinity and Multi-dimensional Assignment for Online Multiple Object Tracking.  In IEEE International Conference on Computer Vision (ICCV), 2019\.
  * [6] Carl Doersch, Abhinav Gupta, and Alexei A Efros.  Unsupervised Visual Representation Learning by Context Prediction.  In IEEE International Conference on Computer Vision (ICCV), 2015\.
  * [7] Carl Doersch and Andrew Zisserman.  Multi-task Self-Supervised Visual Learning.  In IEEE International Conference on Computer Vision (ICCV), 2017\.
  * [8] Weitao Feng, Zhihao Hu, Wei Wu, Junjie Yan, and Wanli Ouyang.  Multi-object tracking with multiple cues and switcher-aware classification.  arXiv preprint arXiv:1901.06129, 2019.
  * [9] Basura Fernando, Hakan Bilen, Efstratios Gavves, and Stephen Gould.  Self-supervised video representation learning with odd-one-out networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
  * [10] Andreas Geiger, Philip Lenz, and Raquel Urtasun.  Are we ready for autonomous driving? The KITTI Vision Benchmark Suite.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012.
  * [11] Shyamgopal Karthik, Ameya Prabhu, and Vineet Gandhi.  Simple unsupervised multi-object tracking.  CoRR, abs/2006.02609, 2020.
  * [12] Chanho Kim, Fuxin Li, and James M. Rehg.  Multi-Object Tracking with Neural Gating using Bilinear LSTM.  In European Conference on Computer Vision (ECCV), 2018.
  * [13] Zihang Lai, Erika Lu, and Weidi Xie.  Mast: A memory-augmented self-supervised tracker.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [14] Laura Leal-Taixé, Anton Milan, Ian Reid, Stefan Roth, and Konrad Schindler.  MOTChallenge 2015: Towards a Benchmark for Multi-Target Tracking.  arXiv preprint arXiv:1504.01942, 2015.
  * [15] Hsin-Ying Lee, Jia-Bin Huang, Maneesh Singh, and Ming-Hsuan Yang.  Unsupervised representation learning by sorting sequences.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.
  * [16] Xueting Li, Sifei Liu, Shalini De Mello, Xiaolong Wang, Jan Kautz, and Ming-Hsuan Yang.  Joint-task self-supervised learning for temporal correspondence.  In Advances in Neural Information Processing Systems, volume 32, 2019.
  * [17] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft COCO: Common Objects in Context.  In European Conference on Computer Vision (ECCV), 2014.
  * [18] Qiankun Liu, Qi Chu, Bin Liu, and Nenghai Yu.  GSM: Graph Similarity Model for Multi-Object Tracking.  In International Joint Conference on Artificial Intelligence (IJCAI), 2020.
  * [19] Jonathon Luiten, Aljosa Osep, Patrick Dendorfer, Philip Torr, Andreas Geiger, Laura Leal-Taixé, and Bastian Leibe.  HOTA: A Higher Order Metric for Evaluating Multi-Object Tracking.  International Journal of Computer Vision, 129(2):548–578, 2021\.
  * [20] Santiago Manen, Michael Gygli, Dengxin Dai, and Luc Van Gool.  PathTrack: Fast Trajectory Annotation with Path Supervision.  In IEEE International Conference on Computer Vision (ICCV), 2017\.
  * [21] Anton Milan, Laura Leal-Taixé, Ian Reid, Stefan Roth, and Konrad Schindler.  MOT16: A Benchmark for Multi-Object Tracking.  arXiv preprint arXiv:1603.00831, 2016.
  * [22] Ergys Ristani, Francesco Solera, Roger Zou, Rita Cucchiara, and Carlo Tomasi.  Performance Measures and a Data Set for Multi-Target, Multi-Camera Tracking.  In European Conference on Computer Vision (ECCV), 2016.
  * [23] Nitish Srivastava, Elman Mansimov, and Ruslan Salakhudinov.  Unsupervised Learning of Video Representations using LSTMs.  In International Conference on Machine Learning (ICML), 2015.
  * [24] Carl Vondrick, Abhinav Shrivastava, Alireza Fathi, Sergio Guadarrama, and Kevin Murphy.  Tracking Emerges by Colorizing Videos.  In European Conference on Computer Vision (ECCV), 2018.
  * [25] Xiaolong Wang, Allan Jabri, and Alexei A Efros.  Learning Correspondence from the Cycle-Consistency of Time.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [26] Donglai Wei, Joseph J. Lim, Andrew Zisserman, and William T. Freeman.  Learning and using the arrow of time.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [27] 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 (CVPR), July 2017.
  * [28] Jenny Yuen, Bryan Russell, Ce Liu, and Antonio Torralba.  LabelMe video: Building a Video Database with Human Annotations.  In IEEE International Conference on Computer Vision (ICCV), 2009\.
  * [29] Wenwei Zhang, Hui Zhou, Shuyang Sun, Zhe Wang, Jianping Shi, and Chen Change Loy.  Robust multi-modality multi-object tracking.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
  * [30] Xingyi Zhou, Vladlen Koltun, and Philipp Krähenbühl.  Tracking Objects as Points.  In European Conference on Computer Vision (ECCV), 2020.