Multi-Object Tracking with Unknown and Varying Cardinality

36 concepts34 papers1 proposal

In classical tracking systems, the world is modeled with a fixed set of dimensions. If you are tracking a single airplane using a Kalman filter, your state vector might consist of four values: position and velocity in a two-dimensional plane. If you scale this up to track exactly $N$ targets, you can concatenate their individual states into a single vector of size $4N$.

But what happens when an airplane flies out of sensor range, or a new one enters?

In real-world scenarios—such as autonomous vehicles navigating busy intersections, drones monitoring wildlife, or surveillance systems tracking crowds—the number of targets (known as the cardinality) is both unknown and dynamically changing. As highlighted by Choi et al. in MCMC Particle Filter based Multiple Preceeding Vehicle Tracking System for Intelligent Vehicle, a fluctuating target count creates a variable-dimension state space. Standard matrix operations break down because the size of the state vector itself changes mid-run.

To track objects under these conditions, a system must simultaneously solve two deeply intertwined problems: estimating the total population size and maintaining the unique identities of individual targets over time (Stowell; Milan et al.). This requires moving away from fixed-dimensional vectors toward mathematical frameworks designed from the ground up to handle structural fluidity.

Random Finite Sets: Treating Populations as Sets

One of the most mathematically rigorous solutions to the variable-dimension problem is Random Finite Set (RFS) theory. Instead of representing the joint state of multiple targets as a vector $\mathbf{x} = [x_1, x_2, \dots, x_N]^T$, RFS frameworks treat the state as a finite set:

$$X_t = \{x_{1,t}, x_{2,t}, \dots, x_{n,t}\}$$

In this formulation, both the number of elements $n$ (the cardinality) and the elements themselves (the individual target states) are random variables.

Traditional Vector State (Fixed Dimension):
[ Target 1, Target 2, Target 3, Empty/Null? ] -> Matrix dimensions break if Target 4 arrives

Random Finite Set State (Dynamic Dimension):
{ Target 1, Target 2, Target 3 } -> Naturally expands to { Target 1, Target 2, Target 3, Target 4 }

By modeling the target population as a set, the system bypasses the need to enforce an arbitrary ordering of targets within a vector. More importantly, it allows the state space to naturally expand or contract.

As demonstrated by Nguyen et al. in Online UAV Path Planning for Joint Detection and Tracking of Multiple Radio-Tagged Objects, combining RFS theory with Track-Before-Detect (TBD) filters allows autonomous systems to plan paths and track objects without knowing how many targets exist in an area. Similarly, Zhong et al. leverage RFS filters in A Hybrid Integration Method Based on SMC-PHD-TBD for Multiple High-Speed and Highly Maneuverable Targets in Ubiquitous Radar to propagate the intensity of targets across frames, allowing the system to automatically instantiate or terminate tracks based on the density of sensor measurements.

Nonparametric Bayesian Priors: Infinite Capacity Models

Another powerful way to handle unknown cardinality is through nonparametric Bayesian statistics, specifically Dirichlet Process Mixture Models (DPMM).

In a parametric model, you must specify the number of clusters (targets) in advance. In a nonparametric model, the number of clusters is assumed to be infinite, but a finite dataset will only occupy a finite subset of them. A common intuitive metaphor for this is the Chinese Restaurant Process (CRP). Imagine a restaurant with an infinite number of tables. When a new sensor measurement (a customer) arrives, it can either:

  1. Sit at an already occupied table (be associated with an existing track).
  2. Sit at a completely new table (instantiate a new track birth).

The probability of sitting at an existing table is proportional to how many people are already there, while the probability of choosing a new table is governed by a scaling parameter $\alpha$. This creates a principled probabilistic penalty for creating new tracks, preventing the system from overestimating the target count due to sensor noise.

Measurement Arrival (Chinese Restaurant Process)
 ┌───────────────────────────┴───────────────────────────┐
 ▼                                                       ▼
Sit at Existing Table?                                  Start a New Table?
P ∝ Number of existing measurements                     P ∝ Scaling Parameter α
(Updates an active track)                               (Triggers a target "birth")

Wood utilized this concept in The Dependent Dirichlet Process Mixture of Objects for Detection-free Tracking and Object Modeling, creating a system that discovers and tracks arbitrary objects directly from raw pixels without pre-trained detectors. By linking these Dirichlet processes across time, the model allows clusters to appear, move, and disappear dynamically.

This approach eliminates the need for hard-coded heuristic thresholds. As shown by Luo et al. in Automatic Topic Discovery for Multi-Object Tracking, reframing tracking as an automatic topic discovery problem allows the system to learn the true number of trajectories directly from data. Further adaptations, such as the doubly stochastic models proposed by Sun 0001 et al. in Unsupervised tracking with a low computational cost using the doubly stochastic Dirichlet process mixture model, allow these infinite-capacity models to run efficiently by limiting computational updates to active regions of the state space.

Managing Birth, Death, and Clutter

The primary operational challenge when tracking an unknown population is distinguishing between true target transitions (births and deaths) and sensor imperfections (clutter or occlusions). If a tracking filter is too sensitive, sensor noise will trigger false positive tracks; if it is too conservative, it will fail to detect new targets entering the scene (Mikolajczyk et al.; The Identity Management Kalman Filter (IMKF)).

To solve this, modern frameworks implement adaptive birth mechanisms. Instead of uniformly searching the entire environment for new objects, the filter dynamically calculates a "birth intensity" map based on where unassigned measurements occur.

For instance, Wu et al. developed an adaptive birth mechanism in Multiple fluctuating targets track-before-detect using multi-Bernoulli filter in radar sensor that cancels out the signals of known, strong targets to expose weaker, newly appearing targets in radar data. In maritime environments, Li et al. demonstrated in Multiple Vessel Cooperative Localization Under Random Finite Set Framework With Unknown Birth Intensities that the spatial topology of existing targets can be used to predict where new targets are likely to appear, drastically reducing the rate of false track initializations caused by clutter.

Adaptive Birth Pipeline:
[Raw Sensor Data] ──► [Subtract Known Active Tracks] ──► [Isolate Unassigned Energy] ──► [Compute Birth Intensity Map]

When tracking must happen across a distributed network of sensors without a central coordinator, managing these births and deaths becomes a consensus problem. As explored by Li 0033 et al. in Distributed Expectation Propagation for Multi-Object Tracking over Sensor Networks, nodes must communicate local track births and deaths to maintain a consistent global belief of the total population size without overloading the network's communication bandwidth.

Global Optimization and Graph Formulations

While filtering methods update the target count recursively frame-by-frame, an alternative paradigm approaches unknown cardinality via batch optimization over a sequence of frames. Here, the problem is reframed as finding the optimal paths through a graph where the total number of paths is unknown.

In Globally-optimal greedy algorithms for tracking a variable number of objects, Pirsiavash et al. formulated multi-object tracking as a min-cost network flow problem on a directed acyclic graph. To elegantly handle an unknown and changing number of targets, they introduced virtual source and sink nodes connected to every detection node in the network.

  ┌─────────► [Detection A] ────────┐
  │                                 ▼
[Source] ───► [Detection B] ───► [Sink]
  │                                 ▲
  └─────────► [Detection C] ────────┘
  • An edge from the virtual Source to a detection node represents a target birth.
  • An edge from a detection node to the virtual Sink represents a target death.

By assigning costs to these edges (where entering the source or sink carries a specific penalty), finding the trajectories of an unknown number of objects reduces to finding the globally optimal set of flows through the network. This formulation allows the system to automatically determine the exact number of trajectories that best explains the video sequence, completely avoiding the need for manual track initialization.

This graph-partitioning intuition extends to static images as well. When estimating human poses for an unknown number of people, Pishchulin et al. showed in DeepCut: Joint Subset Partition and Labeling for Multi Person Pose Estimation that body part candidates can be treated as nodes in a graph. By solving an Integer Linear Program (ILP), the graph is partitioned into an optimal number of distinct subsets, simultaneously discovering how many people are in the scene and which body parts belong to whom.

Key Foundational Work

Sensor fusion cognition using belief filtering for tracking and identification (1999) — contributed 2 concept elements to this direction.
Face detection in a video sequence - a temporal approach (2001) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_dynamic_target_count_estimation_a97c6e57,
  title = {dynamic target count estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dynamic-target-count-estimation/rdr_a97c6e57f8994ea3822c84e3d13ada4b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_dynamic_target_count_estimation_a97c6e57_v1,
  title = {dynamic target count estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dynamic-target-count-estimation/rdr_a97c6e57f8994ea3822c84e3d13ada4b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake