# Joint Probabilistic Hypergraph Matching Labeled Multi-Bernoulli Filter for Rigid Target Tracking
## 3 JPHGM-LMB  
Structure information can be used to achieve better tracking performance in scenario that group targets are well-structured, such as tracking scattering centers on a 2D rigid target. Considering predicted positions of each target and measurements as vertices of a hypergraph (the sensor is assumed to measure the position directly for simplicity), then the data association problem can be formulated as a problem of hypergraph matching, see Figure 1a. Hypergraph representation allows us to use structure information for better data association performance. However, if there are missed detections and clutter, the hypergraph matching may produce wrong result as shown in Figure 1b, the underlying reason is that hypergraph matching finds an optimal subgraph of a hypergraph to matching another hypergraph. If there are some targets which are not detected, the maximum common subgraph between two hypergraphs should be found. In this paper, we focus on how to exploit structure information when undetected targets exist. Note, \(\text{HGM}(G,G^{\prime})\) denotes the hypergraph matching between \(G\) and \(G^{\prime}\). The measurement set obtained at time \(k\) is denoted as \(\mathbf{Z}_{k}=[z_{1},z_{2},...z_{M}]\), where \(M\) is the number of measurements, the predicted target set \(\mathbf{X}_{k|k-1}=[x^{1}_{k|k-1},x^{2}_{k|k-1},...,x^{N}_{k|k-1}]\) is generated based on the preset target dynamic motion model, \(N\) is the number of targets. Data association is to seek an optimal matching element \(\mathbf{z}_{i}\in\mathbf{Z}_{k}\) for each \(x^{j}_{k|k-1}\in\mathbf{X}_{k|k-1}\). An association matrix \(\mathbf{A}^{k}_{N\times M}\) is defined, which consists of a set of association events. \[\mathbf{A}^{k}_{N\times M}=\bigcap_{i=1}^{N}\mathbf{b}_{ii_{i}}, \tag{20}\]  
Figure 1: Sketch of hypergraph matching: (**a**) idea situation and (**b**) hostile situation. where \(\mathbf{b}_{i_{l}i_{l}}\) means \(\mathbf{z}_{i_{l}}\) is associated with \(\mathbf{x}_{k|k-1}^{i}\), \(i=1,2,...,N\), \(t_{i}=1,...,M\). As mentioned above, \(\mathbf{Z}_{k}\) and \(\mathbf{X}_{k|k-1}\) can be represented by hypergraphs, each element of \(\mathbf{Z}_{k}\) and \(\mathbf{X}_{k|k-1}\) is the vertex of the hypergraph, data association problem is transformed into the problem of hypergraph matching. Because of missed detections and clutter, the maximum common subgraph between two hypergraphs should be found, data association problem become more challenging. In order to deal with the missed detections, one intuitive idea is to go through all the undetected cases by enumerating all the subsets of \(\mathbf{X}_{k|k-1}\) inspired by JPDA. \[\mathbf{X}_{k|k-1}=\mathop{\cup}\limits_{l=1,\mathbf{y}_{l}\subset\mathbf{X}_{k|k-1}}^{H} \mathbf{y}_{l}, \tag{21}\]  
where \(H\) is total number of the subsets and \(H=2^{N}\). \(\forall\mathbf{y}_{l}\subset\mathbf{X}_{k|k-1}\), \(\mathbf{y}_{l}\) means a hypothesis that targets contained in \(\mathbf{y}_{l}\) are detected, the association result between \(\mathbf{y}_{l}\) and \(\mathbf{Z}_{k}\) can be obtained by hypergraph matching,  
\[\mathbf{\xi}_{l}=\mathrm{HGM}(\mathbf{y}_{l},\mathbf{Z}_{k}), \tag{22}\]  
\(\mathbf{\xi}_{l}\) is a \(|\mathbf{y}_{l}|\times M\) matrix, \(\mathbf{\xi}_{l}(i,j)=\mathbf{\xi}_{l}^{i,j}=1\) if the \(j\)-th measurement of \(\mathbf{Z}_{k}\) is associated with the \(i\)-th target of \(\mathbf{y}_{l}\), otherwise \(\mathbf{\xi}_{l}^{i,j}=0\). \(\mathbf{\xi}_{l}\) can be extended to a \(N\times M\) matrix \(\mathbf{b}_{l}\),  
\[\mathbf{b}_{l}^{i,j}=\left\{ \begin{array}{l l}\mathbf{\xi}_{l}^{\theta_{l}j}&if\ \ x_{k|k-1}^{i}\in\mathbf{y}_{l}\\ 0&if\ \ x_{k|k-1}^{i}\
otin\mathbf{y}_{l}\end{array} \right.\quad i=1,2,...,N,\ \ j=1,2,...,M \tag{23}\]  
where \(\theta_{i}\) is index number of \(\mathbf{x}_{k|k-1}^{i}\) in \(\mathbf{y}_{l}\) if \(\mathbf{x}_{k|k-1}^{i}\in\mathbf{y}_{l}\). If \(\mathop{\sum}\limits_{j=1}^{M}\mathbf{b}_{l}^{i,j}=0\), the \(i\)th target is not detected.