⚡ electrical engineering

The Mean of Multi-Object Trajectories

This paper introduces a Fréchet mean framework for computing the average of single and multi-object trajectories using OSPA-based metrics, develops efficient greedy and Gibbs sampling algorithms to calculate these means, and demonstrates their superior performance in distributed multi-object tracking consensus compared to state-of-the-art methods.

Original authors: Tran Thien Dat Nguyen, Ba Tuong Vo, Ba-Ngu Vo, Hoa Van Nguyen, Changbeom Shim

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tran Thien Dat Nguyen, Ba Tuong Vo, Ba-Ngu Vo, Hoa Van Nguyen, Changbeom Shim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a fleet of ships, and you have 10 different scouts reporting back on the movement of a school of fish. Each scout is using a different type of sonar, has a different level of experience, and is looking from a different angle.

Scout A says the fish are here, but they disappear for a moment and reappear later.
Scout B thinks there are 5 fish, while Scout C thinks there are 7.
Scout D's report is a bit shaky and full of "ghost" fish (noise).

Your job is to figure out: What is the "true" average path of this school of fish?

This is the problem the paper solves. It introduces a new mathematical way to calculate the "Average Trajectory" and the "Average Multi-Object Trajectory."

Here is the breakdown in simple terms:

1. The Problem: You Can't Just "Add" Paths

In math class, if you want the average of the numbers 2, 4, and 6, you add them up and divide by 3. Easy.

But you can't do that with paths.

What if one path is 10 seconds long and another is 50 seconds long?
What if one path has 3 fish and another has 5?
What if the paths are broken up (the fish hide and reappear)?

You can't simply "add" these paths together. The paper asks: How do we find the single "best" path that represents the group?

2. The Solution: The "Fréchet Mean" (The Perfect Meeting Point)

The authors use a concept called the Fréchet Mean.

The Analogy: Imagine you have a group of friends scattered across a city, and you want to pick a meeting spot that minimizes the total walking distance for everyone.

If you pick a spot too far north, the southern friends have to walk too far.
If you pick it too far east, the western friends suffer.
The Fréchet Mean is that perfect spot where the total distance everyone has to walk is the smallest possible.

In this paper, the "distance" isn't just walking; it's a special mathematical ruler called OSPA (Optimal Sub-Pattern Assignment). This ruler is smart enough to measure:

How far apart the paths are (position error).
How many extra or missing objects there are (cardinality error).
How much the paths are broken or fragmented.

The "Average Path" is the one that is, on average, the closest to everyone else's report.

3. The Two Types of Averages

The paper solves this for two scenarios:

The Single Path Average: Imagine 5 people drew a line on a map. The algorithm finds the "perfect" line that sits right in the middle of all 5, smoothing out the wobbles and ignoring the mistakes.
The Group Path Average: Imagine 5 people drew entire maps with multiple lines (fish, birds, cars). The algorithm finds the "perfect" map that represents the group. It figures out which line in Map A corresponds to which line in Map B, even if Map A has an extra line or Map B is missing one.

4. How They Calculate It (The Algorithms)

Calculating this "perfect average" is incredibly hard because there are billions of possible paths to check. The paper offers two ways to solve it:

The Greedy Search (The "Hiker"): Imagine a hiker trying to find the lowest point in a valley. They take a step, check if they are lower, and if yes, they keep going. If not, they try a different direction. They do this until they can't go any lower.
- Pros: Very fast. Good for real-time use (like a self-driving car).
- Cons: Might get stuck in a small dip and miss the deepest part of the valley (though the paper shows it usually finds the right spot).
Gibbs Sampling (The "Lottery"): Imagine throwing darts at a map, but you are more likely to throw darts near the bottom of the valley. You throw thousands of darts, keep the ones that landed lowest, and eventually, you get a very accurate picture of the bottom.
- Pros: Extremely accurate. Almost guaranteed to find the true best answer.
- Cons: Takes a long time (like waiting for a computer to run a simulation for hours).

5. Why This Matters (The Real World Test)

The authors tested this on a simulated network of sensors (like a swarm of drones or satellites) tracking objects.

The Result: Their new "Average" method was significantly better than current state-of-the-art methods.
Why? Current methods often get confused when a target disappears and reappears (fragmentation) or when sensors disagree on the number of targets. The new method acts like a wise judge: it smooths out the noise, ignores the "ghost" targets, and creates a clean, consistent story of what actually happened.

Summary

Think of this paper as inventing a new kind of GPS for groups. Instead of just averaging coordinates (which fails when things move differently), it calculates the "average story" of a group of moving objects. Whether you are tracking space debris, monitoring a herd of animals, or fusing data from a network of security cameras, this method gives you the clearest, most accurate picture of reality by mathematically finding the "center" of all the messy reports.

1. Problem Statement

The paper addresses a fundamental gap in multi-object estimation and distributed sensor fusion: the lack of a rigorous definition and computational method for an "average" (or mean) trajectory and an "average" multi-object trajectory (MOT).

Context: In standard vector spaces, the mean is the sum of points divided by the count. However, in multi-object tracking, trajectories vary in length (fragmentation), cardinality (number of objects), and existence times. Simple arithmetic averaging is undefined because trajectories cannot be added.
Challenge: Existing distributed fusion methods (e.g., Generalized Covariance Intersection, Track-to-Track fusion) often rely on indirect consensus or density averaging, which can be computationally intractable for multi-scan data or fail to handle trajectory fragmentation and cardinality mismatches effectively.
Goal: Define a mathematically sound "mean" for sets of trajectories that minimizes the aggregate distance to all input trajectories, enabling robust consensus in distributed networks.

2. Methodology

The authors propose a framework based on the Fréchet mean generalized to metric spaces, utilizing the Optimal Sub-Pattern Assignment (OSPA) metric family.

A. Theoretical Formulation

Fréchet Mean Definition: The mean $\hat{v}$ is defined as the point that minimizes the sum of distances to all input trajectories $v^{(n)}$ :
$\hat{v} = \arg \min_{u} \sum_{n=1}^N d(u, v^{(n)})^r$
where $d$ is a metric and $r$ is the order (typically 1 for median-like robustness or 2 for mean-like smoothing).
Metric Selection:
- For Single Trajectories: The OSPA Trajectory Metric ( $d_T$ ) is used. It combines state errors (distance between states at common time steps) and cardinality errors (penalty for missing/extra time steps).
- For Multi-Object Trajectories (MOT): The OSPA(2) Metric is used. This extends OSPA to sets of trajectories, handling both the assignment of trajectories between sets and the cardinality mismatch of the sets themselves.

B. Computational Algorithms

The optimization problem is non-convex and combinatorial (involving existence history and state assignment). The paper proposes two solution strategies:

Greedy Search (Deterministic & Efficient):
- Transformation: The problem is transformed from optimizing over the space of trajectories to optimizing over binary existence vectors ( $\gamma$ or $\eta$ ) and state vectors.
- Mechanism:
  - Trajectory Mean: Iteratively flips bits in the existence vector (0 to 1 or 1 to 0) if it reduces the cost function. Once the existence history is fixed, the optimal state at each time step is computed analytically as a weighted Fréchet mean of the existing input states.
  - MOT Mean: Alternates between optimizing the existence list (adding/deleting trajectories) and the assignment permutation (matching input trajectories to the mean trajectories).
- Complexity: Significantly lower than exhaustive search, making it suitable for online applications.
Gibbs Sampling (Stochastic & Near-Optimal):
- Purpose: To benchmark the greedy solution and approach the global optimum.
- Mechanism: Samples from a distribution proportional to $e^{-\alpha \cdot \text{Cost}}$ .
- Innovation: To handle the permutation space (matching trajectories), the authors introduce a repeated insertion technique. This reparameterizes permutation vectors into insertion vectors, allowing efficient coordinate-wise Gibbs sampling on the space of permutations.

3. Key Contributions

Formal Definition: Introduced the first rigorous definition of the mean for both single trajectories and multi-object trajectories using the Fréchet mean and OSPA-based metrics.
Efficient Algorithms: Developed greedy search algorithms for computing these means, reducing a complex combinatorial problem into tractable steps involving binary optimization and state averaging.
Stochastic Optimization: Proposed a Gibbs sampling framework with a novel repeated insertion technique for sampling permutations, providing a near-optimal benchmark.
Consensus Application: Demonstrated the application of these means for distributed multi-object tracking, where the mean serves as the consensus estimate fusing data from multiple heterogeneous sensor nodes.

4. Experimental Results

The methods were tested in a distributed multi-object tracking scenario with 8 sensor nodes (using different tracker types: TO-MHT, LMB, GLMB) and 20 ground truth trajectories.

Performance Metrics: Evaluated using the OSPA(2) metric (penalizing localization, cardinality, and fragmentation errors) and execution time.
Comparisons: Compared against state-of-the-art methods: DBSCAN-T (clustering-based) and Track Consensus (TC).
Findings:
- Accuracy: The proposed Fréchet Mean (FM) methods achieved significantly lower OSPA(2) errors (~~11m) compared to DBSCAN-T (~~38m) and TC (~49m).
- Robustness: FM methods effectively suppressed noise and outliers and handled track fragmentation better. TC suffered from track switching, while DBSCAN-T showed delays in track initiation/termination.
- Efficiency: The Greedy Search implementation was orders of magnitude faster than Gibbs sampling (seconds vs. thousands of seconds) while maintaining accuracy very close to the Gibbs solution (within ~1m OSPA error).
- Order Sensitivity: The first-order mean ( $r=1$ , median-like) was slightly more robust to noise than the second-order mean ( $r=2$ , mean-like), though $r=2$ was computationally faster.

5. Significance

Theoretical Advancement: This work bridges the gap between statistical theory (Fréchet means) and multi-object tracking, providing a geometric foundation for "averaging" complex data structures like trajectories.
Practical Impact: The proposed consensus algorithm allows distributed networks to fuse data from heterogeneous sensors (different tracker types, different noise models) without requiring a central fusion center or complex density updates.
Scalability: The greedy algorithm makes batch-processing of trajectory data feasible for real-time or near-real-time distributed systems, overcoming the "curse of dimensionality" associated with multi-scan density fusion.
Future Potential: The framework is applicable to any scenario requiring consensus on time-varying sets of objects, including space exploration, surveillance, and cell biology, particularly in networks with unknown or non-common fields of view.