Label Space Partition Selection for Multi-Object Tracking Using Two-Layer Partitioning ^††thanks: $\ast$ Corresponding author

The GLMB filter is designed to estimate object trajectories by modeling the multi-object state with labeled RFS. In particular, a multi-object state X is a collection of the single-object state $\textbf{x}=(x,\ell)$ where $x\in\mathbb{X}$ is its kinematic state, and $\ell$ is a distinct label in some discrete label space $\mathbb{L}$. We define a projection $\mathcal{L}:\mathbb{X}\times\mathbb{L}\rightarrow\mathbb{L}$ by $\mathcal{L}((x,\ell))=\ell$. A set X of labeled objects has no duplicate labels if X and its labels $\mathcal{L}(\textbf{X})=\{\mathcal{L}(\textbf{x}):\textbf{x}\in\textbf{X}\}$ have the same cardinality, i.e., $|\mathcal{L}(\textbf{X})|=|\textbf{X}|.$ In other words, if the labels are distinct we have $\Delta(\textbf{X})\triangleq\delta_{|\textbf{X}|}(|\mathcal{L}(\textbf{X})|)=1,$ where the generalized Kronecker delta function is defined as

(with arbitrary argument, i.e., set, vector or scalar). Besides, the integral of a function $\textbf{f}:\mathcal{F}(\mathbb{X}\times\mathbb{L})\to\mathbb{R}$ is given by $\int\textbf{f}(\textbf{x})d\textbf{x}=\sum_{\ell\in\mathbb{L}}\int_{\mathbb{X}}\textbf{f}((x,\ell))dx.$

For compact expression, following [13], we define the multi-object exponential as

and the set inclusion function follows as

The GLMB filter propagates the GLMB (multi-object) density of the form

where: $\Xi$ is a discrete index set; $p^{(\xi)}(\cdot,\ell)$ is a probability density; and $w^{(\xi)}(I)$ is non-negative weight that satisfies $\sum_{\xi\in\Xi}\sum_{L\in\mathcal{F}(\mathbb{L})}w^{(\xi)}(L)=1$ with $\mathcal{F}(\mathbb{L})$ is all finite subsets of $\mathbb{L}$ including the empty set. The GLMB filter is a closed-form multi-object tracking filter since the prior and the filtering densities are both GLMB families. At each time step, the number of terms in the filtering GLMB density grows exponentially, hence only significant components (ones with high weights) are retained to meet the computational constraint.

In the standard GLMB filter implementation, the computational demand grows significantly when the number of objects increases since the filter complexity is at least in the square number of objects[43]. The primary computational bottleneck occurs during the measurement update stage, with statistical dependence mainly arising from uncertainty in the associations between measurements and objects. This challenge is especially pronounced in dense scenarios where objects are close to each other.

Nevertheless, in practice, objects often travel in groups (i.e., pedestrians, flock of birds), where each group can be assumed to be well-separated from the other. Exploiting this fact, a scalable implementation of the GLMB filter [19] approximates the GLMB density by a product of GLMBs for relatively independent groups of objects. It reduces the complexity to the logarithmic magnitude in the number of objects from the quadratic magnitude in the standard implementation.

Let $\mathfrak{L}$ be some partition of the label space $\mathbb{L}$. A labeled RFS density on $\mathcal{F}(\mathbb{X}\times\mathbb{L})$ is considered as $\mathfrak{L}$ -partitioned GLMB density $\boldsymbol{\pi}_{\mathfrak{L}}$ if it can be expressed as a product of GLMBs (each defined on $\mathcal{F}(\mathbb{X}\times L)$, for $L\in\mathfrak{L}$), as follows

If the current filtering density is an $\mathfrak{L}$-partitioned GLMB, the new filtering density $\boldsymbol{\pi}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$ at the next time step is a standard GLMB [19], not suitable for scalable implementation. To maintain the scalability, the new filtering density can be approximated by an $\mathfrak{L}$-partitioned GLMB. Nevertheless, since the current partition $\mathfrak{L}$ might not be a suitable partition for approximating the new filtering density, the goal is to find the optimal partition $\mathfrak{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$ of the next time step label space $\mathbb{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$ (in some statistical sense) in the space of all possible partitions of $\mathbb{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$ (denoted as $\mathcal{P}(\mathbb{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}})$) for the new filtering density.

Label partitioning in the scalable GLMB filter [19] aims to find a partition of the labels to minimize the amount of potential measurement sharing between objects in different groups. Naturally, labels that are well-separated in the measurement space exhibit low statistical dependence because the likelihood of these labels producing closely spaced measurements is minimal. Here, “well-separated” means the distance between trajectories of labels is significantly larger than measurement noise and predicted object position uncertainty. Assume each factor $\boldsymbol{\pi}^{(L)}_{\mathfrak{L}}$ has the following form:

Then at the next time step, the distribution of the predicted measurement of each label $\ell\in\mathbb{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$ is given by

where $p_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}(x,\ell)$ is the predicted state and $g(z|x,\ell)$ is the single-object measurement likelihood function.

For each label $\ell\in\mathbb{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$, one can use the distribution $\tilde{p}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}(\cdot,\ell)$ to establish a gating region, $B(\ell)\subseteq\mathbb{Z}$, which holds most of the probability mass for the predicted measurement. These gating regions form the foundation for dividing the new label space $\mathbb{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$ into a partition $\mathfrak{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}=\{L_{1},\dots,L_{|\mathfrak{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}|}\}$. Furthermore, to find feasible label partitions, the maximum number of labels within a single partition is constrained by $L_{\text{max}}$, i.e., $|L|\leq L_{\text{max}},\forall L\in\mathfrak{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$. In summary, $\mathfrak{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$ must meet the following conditions [19]:

1. 1.

   For all $L\in\mathfrak{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$ and for any $\ell_{i},\ell_{j}\in L$, either $B(\ell_{i})\cap B(\ell_{j})\neq\emptyset$ or $B(\ell_{i})\cap B(\ell_{1})\neq\emptyset$, $B(\ell_{1})\cap B(\ell_{2})\neq\emptyset$, …, $B(\ell_{n})\cap B(\ell_{j})\neq\emptyset$ for $\{\ell_{1},...,\ell_{n}\}\subseteq L$;

2. 2.

   For all $i,j\in\{1,...,|\mathfrak{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}|\}$ and $i\neq j$, $\big{[}\bigcup_{\ell\in L_{i}}B(\ell)\big{]}\cap\big{[}\bigcup_{\ell\in L_{j}}B(\ell)\big{]}=\emptyset$; and

3. 3.

   For all $L\in\mathfrak{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$, $|L|\leq L_{max}$.

The process involves updating entire prediction gates to decrease the gating probability $P_{G}$ until the specified limit of $L_{\text{max}}$ is reached. Algorithm 1 illustrates the proposed label partitioning process.

Finding $\mathfrak{L}_{\raisebox{0.1pt}{\scalebox{0.6}{+}}}$ poses challenges regarding time complexity due to the necessity of examining all possible label pairs to determine if their predicted gating regions $B(\ell)$, referred to as Gaussian-mixed Minimum Bounding Rectangles (GMBRs), intersect. Additionally, this step must be reiterated until each partition’s maximum label count is no greater than $L_{\text{max}}$. In [19], an R-tree is employed to alleviate the computational complexity of the partitioning, making it feasible for such problems. However, using an R-tree structure for indexing becomes increasingly burdensome as the number of procedure iterations grows [42].

To address these computational challenges, an alternative approach is to employ a grid structure for object indexing and retrieval. Indexing the object with its associated grid can be accomplished with linear time complexity, through algebraic operations [44, 45]. While indexing objects offers computational advantages, the issue of duplicate results arises when objects are assigned to multiple grid-based tiles, necessitating additional processing.

A straightforward approach to eliminate duplicates is by hashing the search results and checking for duplicates within each candidate set [37]. While this method is simple, it can be costly, particularly when dealing with a large number of results. Another widely used method involves using a reference point within the intersection area between each result and the search range. If the reference point falls inside the partition, the result is reported; otherwise, it is discarded [40]. While this method eliminates the need for hashing, we must account for the cost associated with identifying duplicate results and computing the reference point for each of them [42].

We proposed a computationally efficient method for label space partitioning combined with a secondary classifying approach. It possesses a notable advantage in terms of ease of implementation and seamless integration into diverse, complex research projects and large-scale spatial data management systems, facilitating parallel computation. Moreover, it effectively lowers time while consistently delivering robust performance. While this method is applicable to any space-driven partitioning spatial index, we have specifically tailored it for use within a two-dimensional grid structure to optimize label partitioning efficiency.

Algorithm 2 describes the label space partition selection of label partitioning for scalable GLMB filters. Given a set of GMBRs $M$ and grid configuration $\mathcal{G}$, all GMBRs are classified into secondary classes for each tile $t$ in the SecondaryClassifying stage based on III-A1. Following this, the intersection search process begins to find spatially intersecting GMBRs within a specified search range. Here, each GMBR from the set $M$ is used as a search range $w$. During each iteration, relevant tiles intersecting $w$ are selected using algebraic operations in the GetRelevantTiles stage. Within the relevant tiles containing information about the secondary classes, the GetSecondaryClass stage is executed to select the most relevant classes for each tile based on III-A2. By selecting the relevant secondary classes, IntersectingTest stage finds intersected GMBRs with $w$ among a set of GMBRs from these classes. As a result, the TwoLayerLabelPartition function returns label partitions that group GMBRs intersecting with each other. In summary, the secondary classifying technique reduces redundant comparisons, leading to computational efficiency in the label partitioning function.