{'fraction_non_alphanumeric': 0.041866862988220704, 'fraction_numerical': 0.010190638561686298, 'mean_word_length': 3.9876316552323896, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A metric for sets of trajectories that is practical and mathematically consistent

Metrics on the space of sets of trajectories are important for scientists in the field of computer vision, machine learning, robotics and general artificial intelligence. Yet existing notions of closeness are either mathematically inconsistent or of limited practical use. In this paper we outline the limitations in the existing mathematically-consistent metrics, which are based on Schuhmacher et al. 2008, and the inconsistencies in the heuristic notions of closeness used in practice, whose main ideas are common to the CLEAR MOT measures widely used in computer vision. In two steps we then propose a new intuitive metric between sets of trajectories and address these problems. First we explain a natural solution that leads to a metric that is hard to compute. Then we modify this formulation to obtain a metric that is easy to compute and keeps all the good properties of the previous metric. In particular, our notion of closeness is the first that has the following three properties: it can be quickly computed, it incorporates confusion of trajectories' identity in an optimal way and it is a metric in the mathematical sense.


I. INTRODUCTION
Consider two sets A and B each with multiple trajectories. We denote the set of all trajectories as T and the set of all finite sets of trajectories as S. For concreteness, we assume that A = {A 1 , ..., A k } ∈ S and B = {B 1 , ..., B l } ∈ S where each trajectory, say A 1 , is a set of state-time pairs {(t 1 , x 1 ), ..., (t n , x n )} ∈ T with t i ∈ N and x i ∈ R p , which we can also represent as x i = A 1 (t i ). In this paper we propose a new distance measure D(A, B) for A, B ∈ S.
Measures of distance between sets of trajectories are common, for example, in the field of computer vision tracking. In this case A contains the trajectories of several objects and B is the set of approximate trajectories that a tracking algorithm reproduces from video-data. A state-time pair (t, x) can be, for example, the position and velocity of an object at time t. D(A, B) is important to evaluate the performance of multiobject tracking algorithms and to distinguish a good tracker, D(A, B) = "small", from a bad, tracker D(A, B) = "large".
Machine learning is another example where a measure of closeness between sets of trajectories is important. Imagine that each datapoint in a data set is a set of the trajectories followed by all players in a team during a football play. Now consider the following three tasks: the unsupervised task of clustering football plays, the supervised task of building a classifier for the different plays and the information retrieval task of finding plays similar to a reference play. We can solve these tasks using algorithms that only require a measure of distance on the sets of trajectories, e.g. [3], [4], [5] respectively.
Our goal is that D(A, B) is both mathematically consistent and useful in practice. A common mathematical inconsistency of similarity measures used in practical applications involving trajectories is that they are not a mathematical metric. In Section III we show this is the case with the CLEAR MOT measures [2], widely used in computer vision, and hence also with many other distance measures that use heuristics similar to the CLEAR MOT. On the contrary, the measure we introduce satisfies the properties of a metric: for every In the context of tracking, it is easy to see why not dealing with a mathematical metric can lead to inconsistencies. Imagine that under a certain distance D both tracker1's output, O 1 , and tracker2's output, O 2 , are close to the ground truth, GT . In this setting, one intuitively expects that O 1 and O 2 are also close to each other. This expectation is related to the subadditivity property D(O 1 , O 2 ) ≤ D(O 1 , GT ) + D(O 2 , GT ) and we consider its violation an inconsistency. The need for symmetry, non-negativity and the coincidence property is intuitive. Note that the machine learning algorithms mentioned above, namely [3], [4], [5], also require D to be a metric.
In addition to seeking mathematical consistency, our goal is also to define a useful measure. In the examples that follow we again focus on vision tracking because in this context it is clear why the existing mathematically consistent measures, which are based on [1], are not useful in practice.
We obviously want D(A, B) to have a computation time that scales well with the number and length of the trajectories in A and B. We show our metric is fast to compute in Section V-A. In addition, to be useful, D(A, B) must behave as expected in scenarios with intuitive answers as, for example, in the scenarios we now explain. These help us understand how a consistent and practical D should look like, help us introduce relevant previous work, some notation, and also help understanding why our task is not easy.  We can interpret the symbol * as total uncertainty in a tracker A regarding the position of an object B at a particular point in time, in which case we penalize its performance by a fixed amount. If tracker A outputs * because the object B does not exist in that time instant (e.g. it is outside the tracker's range) we do not penalize its performance, hence | * − * | = 0.
More generally, let A + = [..., A + (t), ...] and B + = [..., B + (t), ...] be the vector representation of the single trajectories in A and B, now with each point living in R p , and padded with the symbol * and let d + : R p ∪ { * } × R p ∪ { * } → R be an extension of some point-wise metric d : R p × R p → R such that for every x, y ∈ R we have d + (x, y) = min{2M, d(x, y)}, d + (x, * ) = d + ( * , x) = M > 0 and d + ( * , * ) = 0. One can show that d + is a metric (c.f. Lemma 2 in Appendix B) and hence so is Fig. 1 One way to resolve this ambiguity is to choose the smallest of the values computed, 1.68 in our example. That is, we choose the most favorable comparison between trajectories. The authors in [6] show that this procedure results in a metric. In this paper we call this metric OSPA because it is basically an extension of the OSPA metric of [1]

Scenario 3: For
This metric requires a procedure to match trajectories in A with trajectories in B for comparison and matching (parts of) trajectories is also a central theme in our paper. Indeed, early on researchers identified finding such a match as a central task in defining a metric for sets of trajectories [7], [8].
In the context of computer vision tracking it is important that A and B are extended to have have m = l + k trajectories each. Let A be the ground-truth trajectories and B be the tracker's reconstructed trajectories. We can match any of the k original trajectories in A to a trajectory B + i = {(1, * ), ..., (T, * )}, i > l, to represent that the tracker missed a trajectory completely and we can match any of the l original trajectories in B to a trajectory A + i = {(1, * ), ..., (T, * )}, i > k, to represent the tracker producing a spurious trajectory.
The next scenario shows why OSPA-based metrics can be uninformative in practice.
Scenario 4: For the scenario in Fig. 1-(d), we cannot use an OSPA-based metric to obtain a D(A, B) that is practical in applications such as performance evaluation in computer vision tracking. Indeed, if we use a procedure that matches full-trajectories to full-trajectories as described in Scenario 3, and after we compute the sum of the absolute values of the difference between components of the matched trajectories, we obtain a value of D(A, B) = 7.2. We obtain this value regardless of whether we compare  2 and A 2 with B 1 . Note however that if we compute D(A, C) or D(B, C), where C is an object that is stopped at position 0, we also get 7.2. If we interpret A as the trajectories of two objects and B and C as the output of two different trackers, the OSPA-based metric is saying that the trackers are equally good, yet, most people would probably resist equating both because the tracker that outputs B is actually doing a good job at estimating positions but simply makes one confusion of identity of the objects A 1 and A 2 as they pass by each while the other tracker miss estimates the objects' positions all the time.
OSPA-based metrics tend to over penalize the quality of a tracker in all situations like in Fig. 1-(d) where one trajectory in A follows closely one trajectory in B but later follows another trajectory inB. When this happens we say we have an identity switch and the fact that OSPA-based metrics cannot deal with identity switches makes then useless in many important applications. For example, imagine that we are tracking hundreds of bats, just like the authors [9], [10], [11] did, and we use a tracker that has the impressive ability to simultaneously track all the bats flying around a cave very accurately for many minutes. Only once in a while the tracker confuses the identity of two bats that pass by very close to each other. According to OSPA, the performance of this tracker is very poor. However, probably most people agree that its performance is above that of most existing trackers.
It is because of examples as the above that the computer vision tracking community mostly uses measures of closeness like the CLEAR MOT to assess tracking performance. The CLEAR MOT are in fact two measure of closeness, MOTP and MOTA. Although they are not a metric, they do allow to distinguish good trackers from the bad trackers in realistic scenarios. In particular, they allow the user to control how much identity switches should penalize the value of D(A, B).
The main idea behind the CLEAR MOT is to use a simple heuristic to match parts of trajectories in A to parts of trajectories in B instead of matching full trajectories in A to full trajectories in B like in the OSPA-base metrics. Let Π T be the set of all sequences of length T of permutations of [m] objects. In other words, if Σ ∈ Π T then Σ = (σ(1), σ(2), ..., σ(T )) where σ(t) ∈ Π, ∀t. The CLEAR MOT heuristic sequentially builds a sequence Σ MOT = (σ MOT (1), σ MOT (2), ..., σ MOT (T )) ∈ Π T in such a way that D(A, B), as defined in Definition 2, is small and at the same time the number of times σ(t) is different from σ(t + 1) is also small.

Definition 2. The CLEAR MOT's distance measure for evaluating tracking precision is called MOTP and is defined as
.
The heuristic focuses on simplicity to guarantee that we can compute D(A, B) fast. Unfortunately, at the expense of being computable, it inherits serious limitations as we explain in Section III. It also depends on a user-defined parameter thr that controls how easily σ MOT (t) changes from one time instant to the other. Intuitively, thr allows the user to say how close two objects must be for MOTP to have confidence that they should be compared. Definition 3. The CLEAR MOT matching heuristic defines Σ MOT sequentially as follows.
We call such matches as anchored. Define the non-fixed components of σ MOT (t) such that What is the value of MOTP for an example like in Fig.  1-(d) if thr = 0.19? First we need to compute Σ MOT . Let us focus on the pair A and B. For t = 1 we minimize distance by matching A 1 to B 1 and A 2 to B 2 . This is mathematically equivalent to setting σ MOT (1) = (1, 2). For t = 2 the previous association is anchored because (1)) = 0 < thr and so σ MOT (2) = (1, 2). The same happens for t = 3. For t = 4 the previous association cannot be anchored because that would lead to distances larger than thr so we need to re-minimize the distance. This leads to σ MOT (4) = (2, 1). For t = 5 and t = 6 this association is anchored. In short, we get Σ MOT = ((1, 2), (1, 2), (1, 2), (2, 1), (2, 1), (2, 1)). Using this value we compute D(A, B) = 0. We also get D(A, C) = D(B, C) = 7.2. In other words, MOTP says that, apart from an identity switch, tracker B is better than tracker C, which is the intuitive answer we expect.
Recall that, as we said before, although MOTP defines a measure of closeness between sets of trajectories that is useful, it is mathematically inconsistent. In other words, there is still no measure that is both mathematically consistent and useful in measuring the distance between sets of multiple trajectories. Our main contribution is to show how to capture all the good properties of all the definitions above, and none of their limitations, by using a definition of the form where K : Π T → R is a function that penalizes σ(t) changing with time. With this we fill an important gap in the literature, More comprehensively, our contribution is the following: 1) We show that the CLEAR MOT association heuristic can be unintuitive; 2) We show that MOTP does not define a mathematical metric; 3) We use (1) to define a similarity measure that we prove is a metric and that deals with identity switches optimally; 4) We modify (1) to define the first similarity measure that is fast to compute, is a metric, and is useful in practice; We now present each of our contributions in order. We start however with an extensive literature review to clearly delineate the gap we will fill.
Note that in this paper we repeatedly make reference to the CLEAR MOT measures and OSPA-based metrics. Not because there are no other metrics beside these two but because they are excellent representatives of the two categories in which most the work done in this area falls: similarity measures that are practical (although even these have problems) but are not a metric and similarity measures that are a metric but are not practical.

II. RELATED WORK
In this section we review existing work on metrics for sets of trajectories. Among all the work we review we find no similarity measure between two sets of trajectories A and B that is mathematically consistent (a metric) and, at the same time, is useful and can deal with identity switches (it looks for similarities between parts of trajectories of A and parts of trajectories of B). As we argue in the introduction, these are two desired characteristic that we are the first to incorporate and we focus our discussion around them. Several other ideas in the work we review can be easily incorporated into our work and define new metrics that compete with past work beyond these two characteristics. The discussion of these variant metrics is beyond the scope of this paper.
Our work is related to the problem of defining a distance between two sets A and B, a topic too vast to review in this paper. In [12] the reader can find many of these distances. In this paper, the sets A and B are sets of trajectories, and this limits the scope of our discussion. In the simplest case, when trajectories have only one point/vector, typical definitions involve computing an average of the distance between all pairs of elements from A and B, e.g. [13], or the sum of distance between a few pairs of elements from A and B obtained by some procedure that matches elements of A with elements of B, e.g. [1], [14]. In general however, each trajectory is composed by a set of vectors indexed by time, which limits our discussion even more. To the best of our knowledge the most rigorous works on metrics for sets of trajectories are based on the ideas proposed in [1]. In [1] the authors propose a distance between sets of vectors, the optimal sub-pattern assignment metric (OSPA), and explain its advantages for evaluating the performance of multi-object filters compared to other distances between sets. In particular, the OSPA metric has better sensitivity to cardinality differences between sets than the Hausdorff metric and does not lead to complicated interpretations as the optimal mass transfer metric (OMAT) that [15] propose to address the limitations of the Hausdorff metric. The OSPA metric between two sets of vectors is well defined for any metric between vectors.
All the spin-offs of [1] focus on defining a metric between two sets of trajectories A and B for the purpose of evaluating the performance of tracking algorithms. We recall however that many applications in machine learning and AI apart from tracking benefit if we work with a metric, for example like the ones we define in this paper, rather than a similarity measure that is not a metric. It is crucial to note that all the spin-offs of [1] only compare full trajectories in A to full trajectories in B and hence suffer from the same limitations that we describe in Example 4 in the Introduction.
The authors in [6] define the OSPA-T metric in two steps. In the first step they solve an optimization problem that optimally matches full tracks in A to full tracks in B while taking into account that tracks have different lengths and might be incomplete. In the second step, they assign labels to each track based on this match, they compute the OSPA metric for each time instant using a new metric between pair of vectors that considers both the vectors' components as well as their labels and they sum all the OSPA values across all time instants. Although the optimization problem of the first step defines a metric, [16] point out that the full two-step procedure that defines OSPA-T can violate the triangle inequality.
The authors in [16] define the OSPAMT to be a metric and to be more reliable than OSPA-T when we evaluate the performance of multi-target tracking algorithms. The OSPAMT metric also computes an optimal match between full trajectories in A and full trajectories in B but unlike OSPA-T allows to match one full trajectory in A to multiple full trajectories in B (and vice-versa). The authors make this design choice not to penalize a tracker when it outputs only one track for two objects that move closely together.
Some extensions to OSPA incorporate the uncertainty in the measurements. The Q-OSPA metric defined in [17] incorporates uncertainty by weighting the distance between pairs of points by the product of their certainty and by adding a new term that is proportional to the product of the uncertainties. The H-OSPA metric defined in [18] incorporates uncertainty by using OSAP with distributions as elements of A and B instead of vectors and using the Hellinger distance between distributions instead of the Euclidean distance between vectors. The authors of both works focus only on the simpler case where the sets A and B contain vectors/points and not trajectories. However, combining their work with that of [6] or [16] to obtain a metric between sets of trajectories is immediate.
The papers above are fairly recent and the search for similarity measures between sets of trajectories that are a metric is not older. However, researchers in the field of computer vision have been interested in defining similarly measures for sets of trajectories to evaluate the performance of tracking algorithms much prior to these works. It is impossible to review all work done in this area. Specially because the evaluation of the performance of trackers has many challenges other than the problem of defining a similarity measure. See [19], [20] for some examples of these other challenges. Nonetheless, we mention a few works and point out ideas in them that relate to our problem. We emphasize that none of the following works defines a metric mathematically.
Most of our paper is about solving the problem of forming a good match between elements in A and B. In [7], which is expanded in a subsequent paper [8], the authors are one of the first to identify this as the central problem in defining a similarity measure, although some of their ideas draw from the much earlier Ph.D. thesis of one of the authors [21]. They propose a one-to-one association between the different points of A and B but this association is optimally computed independently every instant and there is no discussion about the number of changes in matching that this might create.
One of the reasons why the CLEAR MOT metrics are widely used is because they create a simple association between A and B, i.e., the association between A and B does not change often in time. It appears that [22] is one of the first works that describes how to control the number of association changes when computing a similarity measure. The authors do not associate A and B independently every time instant but rather use a sequential matching procedure that tries to keep the association from the previous time instant if possible. This is similar to the procedure used in the much more recent CLEAR MOT measures that we discuss in the Introduction.
The association that [22] use at every point in time is not one-to-one optimal like in [7] or in the CLEAR MOT, rather the authors use a simple thresholding rule to associate neighboring elements of A and B. The idea of using a simple threshold rule to compare A and B seems to have survived until relatively recent. For example, in [23] the authors match a full trajectory in A to a full trajectory in B if they are close in space for a sufficiently long time interval. The authors in [24] use a similar thresholding method to match A and B.
Shortly after the papers [7], [8] some of the same authors discuss again the problem of associating A and B. In [25] they propose four different methods to solve this problem. In the first method, A and B are optimally matched independently at each time instant, possibly generating different associations every time instant. In the second method, the association between A and B cannot change with time. This is similar to what happens in the OSPA-based metrics. It creates simple associations but can also lead to problems as we discuss in the Introduction. In the third method, the authors allow the association between A and B to change in time but only in special circumstances. Unfortunately, as they point out, this leads to a NP-hard problem. Finally, in the fourth method, the authors discuss some ad-hoc ideas to try to minimize the number of changes in association. Some of these ideas resemble the idea used in the CLEAR MOT of keeping the association from the previous time period if possible.
Not all challenges in defining a measure of performance for trackers are related to defining a similarity measure between trajectories. In addition, not all challenges in defining a similarity measure between trajectories are related to defining a way to compare and associate the trajectories in A with the trajectories in B. Even if we assume A and B are already matched, there is the question of computing some quantity from this match. A typical quantity researchers compute is the sum of the distances between the different points of matched trajectories, averaged over all pairs of matched trajectories. As explained later, our metric is a combination of this quantity with the number of confusion of identities in the match between A and B.
Apart from other distance-related quantities, researchers also compute many quantities that evaluate the quality of the match itself. For example, the number of trajectories in A that do not match to any trajectory in B or the number of times in which the match between A and B changes. [26], [27] list many quantities that can be computed to measure the similarity between A and B and some of these quantities might be useful to define similarity measures for applications outside tracking.
It is worth mentioning a few works that differ from the main stream in this aspect. One of them is [28], where the authors define a similarity measure based on comparing the occurrence of special discrete events in A and B, and another is [29], where the authors propose an information theoretic measure of similarity between sets of trajectories. Finally, in [30] the authors propose a similarity measured based on hidden Markov models that does not assume that the temporal sampling rates of the trajectories are equal.

III. THE LIMITATIONS OF THE CLEAR MOT
The CLEAR MOT similarity measures are one of the most commonly used measures that are able to associate parts of trajectories of A with parts of trajectories in B such that the sum of the distance between associated points is small and at the same time the association is simple, i.e. does not change often in time. The CLEAR MOT achieve this using the heuristic procedure in Definition 3. In Theorem 1 we show that this heuristic can be unintuitive and in Theorem 2 we show that MOTP is mathematically inconsistent. Theorem 1. For any Σ ∈ Π T and any A, B ∈ S without holes and with m trajectories each let swi(Σ) = In the context of computer vision tracking the theorem above shows that there are situations in which the average tracking performance gets arbitrarily close to optimal with time while the CLEAR MOT association Σ MOT says that it does not. In other words, the CLEAR MOT can be unintuitive.
The following theorem show that, for any thr > 0, the MOTP is mathematically inconsistent.

Theorem 2. MOTP is not a metric.
The proofs of these two theorems are in Appendix A.

IV. A NATURAL METRIC FOR SETS OF TRAJECTORIES
Despite the large volumes of research about similarity measures for sets of trajectories, largely motivated, at least initially, by the need to assess the performance of tracking systems, our work is the first to propose a measure that is both mathematically consistent and practical.
To build towards our final metric, in this section we define a metric that captures the best match between the parts of trajectories in A and parts of trajectories in B while tacking into account that simple matches are preferred to complex ones. As the four scenarios in the introduction suggest, this is a desirable characteristic for a measure of distance and is only partially present in the OSPA and the CLEAR MOT which are representatives of the two currently segregated camps of (a) the consistent metrics and of (b) the practical metrics. Unfortunately the metric we now define is hard to compute and we need an extra section to modify it and reduce computational complexity.
We now introduce a another new definition.
We now define a new distance measure. Definition 5. The natural distance between two sets of trajectories is a map D nat : S × S → R + 0 such that for any Remark 1. This definition is compatible with scaling the term K(Σ) by some constant α > 0. We are not ignoring this possibility but simply put any scaling factor 'inside' K.

Indeed, if K(Σ) satisfies properties (i), (ii) and (iii) then so does αK(Σ).
It is the user's decision to determine, for the application she has in mind, the relative importance of the terms K and d + in (2).
This definition is related to the CLEAR MOT measure in the sense that it builds an association between parts of trajectories in A and parts of trajectories in B such that the distance between associated trajectories is small and the association does not change often in time. It is the term K in the definition of D nat that allows us to control the complexity of the match between the trajectories in A and in B. This guarantees that D nat is as useful in practice as the CLEAR MOT.
This definition is related to the OSPA metric regarding mathematical consistency but is much more general. Indeed, we recover the OSPA metric if we confine ourselves to K = K OSP A defined as K OSP A (Σ) = 0 if Σ = (σ, σ, ..., σ) and K OSP A (Σ) = ∞ otherwise. Using K = K OSP A forces us to compare full trajectories in A to full trajectories in B, something that as we explained in the Introduction, leads to unintuitive results.
Strictly speaking our definition does not define a single measure but a family of measures,one for each choice of d(.) and K(.). The following theorem shows that all the measures in this family are a metric. Its proof is in Appendix B.

Theorem 3. The map D nat is a metric on S.
A natural choice for d is the Euclidian metric, that is, We now show that several desirable definitions for K satisfy the properties in Definition 4. In the context of computer vision tracking, all these K allow to penalize trackers that generate many identity switches.
Perhaps the most obvious definition is for K to count the number of times that the association between A and B changes.
Another two desirable choices for K are (a) the function that sums the minimum number of transpositions to go from one permutation to the next and (b) the function that sums the number of adjacent transpositions to go from one permutation to the next. In what follows k Cayley (σ) gives the minimum number of transpositions to obtain the identity permutation from σ ∈ Π and k Kendall (σ) gives the number of adjacent transposition that the bubble-sort algorithm performs when sorting σ to obtain the identity permutation. The Cayley distance can be traced back to [31] and the Kendall distance to [32].
The proof of Theorems 4, 5 and 6 is in Appendix B.
Although many intuitive choices for K satisfy properties (i), (ii) and (iii) some natural ones to not. For example, given a β ≥ 1 we might want to define K maxcount as K maxcount (Σ) = K count (Σ) if K count (Σ) ≤ β and K maxcount (Σ) = ∞ if K count (Σ) > β (we can replace ∞ by some very large number if we want to be technical about the range of K being R + 0 ). This K basically forces us not to create an association between A and B more complex than a certain amount β, something natural to desire. The following is proved in Appendix B.

Theorem 7. K maxcount does not satisfy (iii).
Even if a function K violates some of the properties it might still be the case that using that function in (2) defines a metric. However, we often find that from a set of associations Σ, Σ ′ that violate some of the three properties in Definition 4 we can build three set of trajectories A, B and C that violate some of the properties required of a metric. This is the case, for example, for K maxcount and d the Euclidean metric.

Theorem 8. If K = K maxcount and d is the Euclidean distance then equation (2) does not define a metric.
The proof of this theorem is in Appendix B. In this sense, the conditions in Definition 4 are both necessary and sufficient for equation (2) to be a metric.
Some choices for d and K lead to a metric D nat that is easy to compute D nat . For example, if we choose K = K OSP A and d to be the Euclidean distance then D nat reduces to OSPA metric which can be solved in polynomial time using, for example, the Hungarian algorithm [33] (cf. [1]). Unfortunately, many desirable choices for K and d lead to a hard problem. For example, if d is the Euclidean distance and K = K count or K = K Cayley or K = K Kendall then computing D nat is related to solving a multi-dimensional assignment problem that is HP-hard [34].
We solve this issue in the next section where we modify D nat to obtain a new metric that is as easy to compute as solving a linear program (recall that all LPs can be solved in polynomial time [35]).

V. A NATURAL AND COMPUTABLE METRIC
First we introduce some notation. Given A, B ∈ S we define A + and B + just like in Section IV. We define T and m accordingly. Given d we also define d + like in Section IV. Let P be the set of all doubly stochastic matrices, that is, P = {W ∈ R m×m : W † 1 = 1, W 1 = 1, 0 ≤ W ≤ 1}. Let P T be the set of all sequences of length T of doubly stochastic matrices. Given A, B ∈ S and t ≤ T we define the matrix D AB (t) ∈ R m×m as (D AB (t)) ij = d + (A + i (t), B + j (t)). Let be a matrix norm that satisfies the following property for any four matrices X 1 , Note that this is analougous to property (iii) that we use for K in Section IV.

Definition 6. The natural computable distance between two sets of trajectories is a map
Remark 2. This definition is compatible with scaling the first term by some constant α > 0. We are not ignoring this possibility but simply put any scaling factor "inside" the matrix norm. In Section VI we solve (4) for different values of α to obtain a trade-off plot between its two terms.
The motivation for this definition is to obtain a measure that is as similar as possible to D nat but that we can compute fast. Just like MOTP and D nat , the measure D comp also builds an association between parts of trajectories in A and parts of trajectories in B. This association is represented by the matrices W (t). However, unlike Σ in D nat , the W matrices also give us a weight/strength for the different matches between A and B. Just like D nat , and as the next theorem shows, D comp is also mathematically consistent.

Theorem 9. The map D comp is a metric on S.
The proof of this theorem is in Appendix C. Most importantly, unlike D nat , computing D comp amounts to solving a convex optimization problem. In short, D comp combines all the advantages of OSPA, MOTP and D comp .
The following Lemma gives sufficient conditions for a metric . to satisfy property (3). See Appendix C for a proof. This lemma implies, for example, that the 1-norm and ∞norm spectral norm for matrices are valid choices for . . In particular, the use of . 1 in D comp is extremely useful because it induces the changes of association to be sparse in time and, as the next theorem shows, it reduces D comp to solving a linear program. The theorem's proof is in Appendix C. The metric D comp allows to consider a scaling factor α in front of the term t W (t + 1) − W (t) , which we call the switch term, swi. We call the other term the distance term dist. Like the thr value in the CLEAR MOT, α allows us to penalize heavily the error in distances in some applications (α = small); and in other applications allows us to penalize heavily the number of associations switches (α = large). One can however report how close a set A ∈ S is from B ∈ S without choosing a specific α, simply plot the tradeoff curve between swi and dist as a function of α. The closer this curve is to the left/bottom edges of the positive quadrant of the cartesian plane, the closer A to B.
The next theorem shows that the tradeoff curve produced by the two terms of D comp , which we denote by (swi Dcomp (α), dist Dcomp (α)), is, in a sense, the best trade-off curve between dist and swi that any metric can generate. To state the theorem we need to define the region R of pairs of distance-value and switch-value that we can improve upon with some stochastic matrices {W (t)} produced by some association procedure of some similarity measure. More concretely, The proof of following result is in Appendix C.

Remark 3.
In the proof of the above theorem we show that R is convex. Hence, because the boundary of R is by definition Pareto efficient, this boundary must be a convex nonincreasing curve. Since the curve (dis Dcomp (α), swi Dcomp (α)) effectively covers this boundary, we can use this property to efficiently estimate the trade-off curve. Basically, we can compute (dis Dcomp (α), swi Dcomp (α)) for some discrete set values of α and then we can take the convex hull of these points.

A. Computing D comp in practice
There are multiple ways to compute D comp in practice, all of which amount to solving a convex optimization problem. For this paper we coded a solver in C based on the Alternating Direction Method of Multipliers (ADMM) because the ADMM is known to scale well for large problems and its modular nature makes it easy, in future work, for us to research variants of the formulation D comp without having to re-write much of our code. For a good introduction to the ADMM, related methods and applications see [36]. Our implementation is approximately ×50 faster than using Matlab CVX [37].
In Figure 2 we show the run-time of our code as a function of the total duration T of the input data for a different number of free association variables W ij (t) per time instant t. We use the terminology "free association variables" to emphasize that some W ij (t) might be a priory set to zero if the distance between point i and point j at time t is very large, which can save computation time. In the figure we choose the euclidean distance for d(., .) and the one-norm for matrix norm . in the switch term. Similar run-times hold for other metrics. The runtime is computed for randomly generated sets of trajectories on a single core of a 1.4GHz Intel Core i5 MacBook Air. In our tests, the ADMM always converged to 1% accuracy in less than 150 iterations.
To interpret the plots, imagine you want to evaluate the quality of a tracker when tracking 22 players in a soccer field. Imagine that the tracker operates at 30 frames per second and also that your tracker is noisy so that it produces a few false tracks that create approximately 10 extra points per instant. To compute D comp , and after you extend the ground-truth and hypothesis sets from A and B to A + and B + , you are dealing with distance matrices with about ((22 + 10) × 2) 2 = 4096 variables per instant t. Using Fig. 2 you can conclude that it will take you about 40 seconds to evaluate the accuracy of 800/30 = 26.6 seconds of data if you use a C implementation of the ADMM on a 1.4GHz MacBook Air. If you reduce the number of free variables per frame to half by setting W ij (t) to zero if point i and j are larger than a given threshold then you can reduce the time to process 26.6 seconds of data to about 20 seconds.

VI. MORE NUMERICAL RESULTS
To the best of our knowledge, D comp is the first similarity measure that is a mathematical metric and deals with identity switches in an optimal way while being computable in polynomial time. In particular, we can use it to generate optimal tradeoff curves between dist and swi (c.f. Theorem 11).
To illustrate this point we now use D comp to assess the closeness between sets A and B both synthetically generated and coming from a tracking application and compare it with MOTP. We make the comparison through dist-swi tradeoff plots. For D comp we use the extended Euclidean metric for d + , the component-wise 1-norm for . and the tradeoff curve is parametrized by a multiplying factor α > 0 that we put in front of the switch term. For the MOTP, we compute the value for and swi in the same way as for D comp but using the MOT heuristic association between A and B described in Definition 3. The MOTP tradeoff curve is parameterized by thr.
A direct interpretation of our results is that D comp is better than MOTP. However, a more important interpretation of our results is that D comp builds better associations between A and B than the greedy associations that are widely used in the literature and the non-greedy association that do not allow   [26], [27].

A. Real trackers and real data
In Figure 3-(a) we show the performance of the trackers in [38] and [39] on the AVG-TownCentre data set. We call these trackers T racker09 and T racker11 respectively. The data set is part of the Multiple Object Tracking Benchmark [40] that is widely used in computer vision. It comes from a pedestrian street filmed from an elevated point at a resolution of 1920 × 1080 for 3 minutes and 45 seconds and can be downloaded from [41]. In Figure 3-(b) we show the performance of the trackers in [42] and [43] on the PETS2009 data set, also part of the Multiple Object Tracking Benchmark. We call these trackers T racker12 and T racker15 respectively. Its resolution is 768 × 576, its duration is 1 minute and 54 seconds and it can be downloaded from [44]. We produced all the plots using the exact same output that each tracker produced in its respective paper thanks to the authors who provided us with their trackers' output. For computing we set M = 20 for AVG-Towncenter and M = 50 for PETS2009.  Fig. 3. (a) -swi tradeoff plot for T racker09 and T racker11 on the AVG-TownCenter data set; (b)dis-swi tradeoff plot for T racker12 and T racker15 on the PETS2009 data set. All the curves go to swi = 0 for large dist.
As expected from Theorem 11, the tradeoff curves from MOTP understate the performance of the trackers. In particular, all trackers are achieving substantial smaller number of switches without incurring in larger distance costs that what MOTP reports. Interestingly, for these trackers and datasets D comp keeps the same relative ordering of performance as MOTP, although it is conceivable that there are situations in which a tracker 1 is better than a tracker 2 according to MOTP but not according to D comp . It would be interesting to find such an example. Finally notice that although the difference between the curves is large in absolute value, in relative values the curves are not very different. The absolute values are large because both and swi terms are sums of distances and switches over all tracks and over all time instants and the relative values are small because all trackers are state-of-the-art and perform almost as well as possible.

B. Random ensemble of trajectories
In the examples above A and B are relatively close to each other because the trackers are all good trackers. In this section, to better appreciate the behavior of D comp , we randomly generate a set A with 25 trajectories (slightly more than e.g. the number of players in a football game) and then a set B of trajectories that are a distorted version of the trajectories in A. We generate the trajectories in A by randomly starting and ending a trajectory in time and having the object in that trajectory randomly change its velocity's direction along the way. The trajectories in B are generated by randomly fragmenting the trajectories in A, randomly removing some of the resulting trajectories, randomly adding noise to all trajectories and randomly flipping or not the ID of two trajectories if they pass by each other close enough. In the end, B might have more or less than 25 trajectories. In total we have four knobs to increase/reduce the distance between A and B: the amplitude of noise, AM P noise, the probability of fragmenting a track at each point in time, F RAGprob, the probability of deleting a points in the track, DELprob, and the threshold distance after which we allow to tracks ID to be switched or not randomly, SW Idist.
These random trajectories are far more diverse than the trajectories in most publicly available data sets because real objects, like people, have fairly simple trajectories In addition, we do not just test two datasets, like in Section VI-A, but we datasets form about 20 different levels of distortion for each of the 4 knobs described above and for each of these levels of distortion we test 30 random sets A and B. Hence, if you will, and in the context of computer vision tracking, it is as if we test 2400 different data sets of ground-truth and hypothesis trajectories.
We study the similarity between the random sets A and B using dist-swi trade-off plots. The smaller the area under the curve of a the trade-off plot, the more similar A and B are. In Figure 4 we show the average area under the trade-off curve (AUC) for the random sets A and B under the different knob setting. The AUC is normalized by the largest AUC possible. The largest AUC is the product of the largest distance-error possible with the largest switch-error possible. Each point in the plots is an average over 30 random pairs A and B with the same knobs setting. In each plot we keep all but one knob constant.
As expected from Theorem 11, the AUC of D comp is smaller than the AUC of MOTP. Note that it is incorrect to interpret these results as saying that MOTP is a like a scaled version of D comp . Recall that we use the same d + to measure the distance between points in space in both MOTP and D comp . We also compute the number of switches that the association of MOTP produces in the same way that we compute the number of switches that the association in D comp produces. The difference in the curves of Figure 4 as a much deeper significance than a simple rescaling: for the 600 random pairs that we test, which consider different kinds of distortions between A and B, and if we interpret each A and B as the ground-truth and output of a tracker, MOTP always says that the tracker is worse than it actually is. The D comp can see similarities between A and B that the MOTP cannot.

VII. CONCLUSION
The problem of defining a similarity measure between sets of trajectories is crucial for computer vision, machine learning and general AI. An essential aspect in defining a similarity measure is finding a good and simple association between the elements of the sets. Existing similarity measures that define useful associations fail to be a metric mathematically speaking and the ones that are a metric only consider very primitive associations: full trajectories to full trajectories. The metric D comp is the first that simultaneously (1) is a metric, (2) compares parts of trajectories to parts of trajectories, (3) allows to control the complexity of the association between trajectories in an globally optimal way and (4) can be computed in polynomial time.
The general idea of defining mathematical metrics for sets of trajectories using convex programs is our greatest overarching contribution. The next step is to explore variants of our metric that allow to incorporate uncertainty, as well as richer comparisons between A and B without losing its good properties.

APPENDIX A THE LIMITATIONS OF THE CLEAR MOT
Proof of Theorem 1. We will construct an example for which the theorem is true. Our example proves the theorem for any 1 < thr < 2 and for A = {A 1 , A 2 } and B = {B 1 , B 2 }, i.e. m = 2, where A i and B i are trajectories living in 1D. We explain how to generalize this example to any thr and any m at the end.
Consider two sets of one-dimensional trajectories A = {A 1 , A 2 } and B = {B 1 , B 2 } defined as in Figure 5 but where the trajectories extend beyond instant 15 until time T .
The number of times that σ MOT (t) = σ MOT (t + 1)  {(1, 2), ..., (1, 2)} because (1) we start with {A 1 ↔ C 1 , A 2 ↔ C 2 }, (2) the association A 1 ↔ C 1 is always anchored because the distance between A 1 and C 1 is always zero and thus always smaller than thr > 1 and (3) after some point between instant 4 and instant 12, when the distance between A 2 and C 2 exceeds thr < 2, MOTP still keeps the association A 2 ↔ C 2 because A 1 and C 1 are already anchored. This association leads to D(A, C) < 8.5 T . Therefore, for T large enough we have D(A, B) > 2(T −12) T > 8.5 T + 8.5 T > D(A, C) + D(C, B).

APPENDIX B A NATURAL METRIC FOR SETS OF TRAJECTORIES
To prove Theorem 3 we need the following Lemma.
To prove the coincidence property observe that d + (x, x ′ ) = 0 either implies that , follows directly from the definition. To prove the subadditivity property we need to consider eight different cases. It is trivial to check that the following six cases satisfy the triangle inequality: We check the two other cases separately. If Remember that A and B are unordered sets of trajectories so A = B means that there is an isomorphism between A and B. In other words, they are equal apart tom a relabeling of their elements. If A = B and we set Σ = (σ, σ, ..., σ) where σ is an isomorphism between A and B, then the objective in (2) is equal to zero. Since the minimum of (2) must always be non-negative, we conclude that A = B ⇒ D nat (A, B) = 0. Now assume that D nat (A, B) = 0 and let Σ * = (σ * (1), ..., σ * (T )) be a minimizer of (2). D nat (A, B) = 0 implies that K(Σ * ) = 0 and therefore σ * i (t) = σ * i (1) for all t and i. Since the labeling of the trajectories does not matter in computing D nat , we assume without loss of generality that their labeling is such that we can write σ * i (t) = i. D nat (A, B) = 0 also implies that, for all t and i, we have d Since d + is a metric this in turn implies that A + i (t) = B + i (t) for all i and t, which is the same as saying that A + = B + . If A = B then A + = B + therefore A + = B + implies that A = B. To be more specific, A is equal to B apart from a relabeling of its trajectories, which we can do because A and B are unordered sets of trajectories. Symmetry property: D nat only depends on A and B through d + and, like all metrics, this is a symmetric function. In addition, if we swap i and σ i (t) in (2) the minimum of (2) remains unchanged. It follows that D nat (A, B) = D nat (B, A). Subadditivity property: We prove that D nat (A, C) ≤ D nat (A, B) + D nat (B, C). Since d + is a metric, we can write that for any Σ ′ = (σ ′ (1), ..., σ ′ (T )) ∈ Π T and for all i and t. Now notice that Using this together with (5) we can write .
. This means that Σ ′′ = Σ ′ • Σ. We can use Σ ′ to rewrite the above expression as If we use the second and third property that K satisfies we can also write Now we add both sides of (6) and (7) and ). Finally, we find the minimum of both sides of the inequality over all pairs of Σ and Σ ′ . Recall that we can choose Σ ′ independently of Σ. Since for every pair (Σ, Σ ′ ) there is exactly one pair (Σ ′ , Σ ′′ ), finding the minimum over Σ and Σ ′ is the same as finding the minimum over Σ ′ and Σ ′′ . Therefore we get, which is the same as D nat (A, C) ≤ D nat (A, B) + D nat (B, C).
Proof of Theorem 8. We produce three sets of trajectories A, B and C that make (2) violate the triangle inequality. In this proof we assume β = 1 but it is easy to change A, B and C such that the proof holds for any β, 1 . Let I = (1, 2) be the identity permutation and let σ 0 = (2, 1) be the permutation that swaps 1 and 2.  The optimization problem D nat (A, B) has a minimum of 1 at Σ = (I, σ 0 , σ 0 ). The optimization problem D nat (B, C) has a minimum of 1 at Σ = (I, I, σ 0 ). When we solve the optimization problem D nat (A, C) we are only allowed to perform one change in the association between A and C, otherwise the term K maxcount makes us pay a very large cost. With only one change in the association, we incur in a distance of 4 for t = 1 or t = 2 or t = 3. Hence, D nat (A, C) ≥ 4 > 1 + 1 = D nat (A, B) + D nat (B, C).

APPENDIX C A NATURAL AND COMPUTABLE METRIC
Proof of Theorem 9. Let A, B and C be any three elements of S. Coincidence property: If D comp (A, B) = 0 then W (t) = W (1) for all t. Hence, if D comp (A, B) = 0 then D AB (t) ij = 0 for all i, j such that W (1) ij > 0. Now recall that if W ij is a doubly stochastic matrix then there exists a permutation σ ∈ Π such that W iσi > 0 for all i. Therefore, there exist σ ∈ Π such that D AB (t) iσi = 0 for all t and i. In other words, A and B are the same apart from a relabeling of their elements. Symmetry property: Using the properties of tr we have that tr(W † (t)D AB (t)) = tr((W † (t) D AB (t)) † ) = tr(D AB (t) † W (t)) = tr(D BA (t)W (t)) = tr(W (t)D BA (t)). Minimizing with respect to {W (t)} is the same as minimizing with respect to {W (t) † } so D comp (A, B) = D comp (B, A). Subadditivity property: We prove that D comp (A, C) ≤ D comp (A, B) + D comp (B, C). First note that, since d + is a metric we have that D AC (t) ij ≤ D AB (t) ik + D BC (t) kj for any k. Let {W 1 (t)}, {W 2 (t)} ∈ P T . We multiply both sides of the previous inequality by W 1 (t) ik W 2 (t) kj and sum over ijk and obtain m i,j,k=1 W 1 (t) ik W 2 (t) kj D AC (t) ij ≤ m i,j,k=1 W 1 (t) ik W 2 (t) kj D AB (t) ik + m i,j,k=1 W 1 (t) ik W 2 (t) kj D BC (t) kj . Note that W 1 (t) and W 2 (t) are doubly stochastic matrices therefore we have m j=1 W 2 (t) kj = 1 and m i=1 W 1 (t) ik = 1 and we can re-write the previous inequality in matrix for as tr((W 1 (t)W 2 (t)) † D AC (t)) ≤ tr(W 1 (t) † D AB (t)) + tr(W 2 (t) † D BC (t)). From the definition of we have that W 1 (t + 1)W 2 (t + 1) − W 1 (t)W 2 (t) ≤ W 1 (t + 1) − W 1 (t) + W 2 (t + 1) − W 2 (t) . Summing both sides of the last two inequalities and, summing over t, and minimizing over {W 1 (t)}, {W 2 (t)} ∈ P T we have that