# Multi-Player Tracking for Multi-View Sports Videos with Improved K-Shortest Path Algorithm
## 3 Methodology
### Proposed KSP-AF Formulation  
According to the original KSP, we first need to discretize the basketball court into \(G\) grid cells. If the frame number of one batch is represented as \(F\), the total number of nodes except the two virtual nodes is \(n=GF\). The approach tactfully formulates the multiple objects tracking problem as a k-shortest node-disjoint paths problem on a directed, acyclic graph. The nodes represent the human locations in the court and edges denote the possible move for players in consecutive frames, while the weights between nodes pairs are determined by the human occupied probability of every node. After the construction of the graph, \(k\) paths between these nodes can be found, as the total costs of the paths are minimum. In this part, we analyze how to take two or more appearances into consideration based on the KSP tracking algorithm. Assume that we have access to a person detector that estimates the probability of presence of someone at every location \(i\). Then the player occupied probability for each grid can be formula as:  
\[\rho_{i}^{t}=P(X_{i}^{t}=1|I^{t}), \tag{2}\]  
where \(\rho_{i}^{t}\) is the estimated probability of a location i to be occupied by a player at time \(t\), \(X_{i}^{t}\) is a random variable standing the true occupancy of location \(i\) at time \(t\), and \(I^{t}\) represents the original image at time \(t\). Moreover, what we need to consider in our tracking algorithm is not only the occupied probability of each location, but also more informative features for each grid cell occupied by a player. Thus, we further assume that we can compute an appearance feature model \(Y_{i}^{t}\) and that we use it to estimate the identity similarity between two node pairs in consecutive frames:  
\[s_{i,j\in\mathbb{N}}^{t}=P(Y_{i}^{t}=Y_{j\in\mathbb{N}}^{t+1}|I_{t},X_{i}^{t}=1), \tag{3}\]  
where \(s_{i,j}^{t}\) is the similarity that the identity information in location \(i\) at time \(t\) is the same as the location \(j\in\mathbb{N}(i)\) at time \(t+1\); \(\mathbb{N}(i)\) is the neighborhood of location \(i\); and \(Y_{i}^{t}\) and \(Y_{j}^{t+1}\) are appearance features of location \(i\) and location \(j\in\mathbb{N}(i)\) at time \(t\) and \(t+1\), respectively. As our goal is to find a set of physically possible trajectories that each trajectory contains only one player, on one hand we need to link the detections as many as possible, and, on the other hand, the similarity between the connected nodes should be as high as possible. We can formulate it as:  
\[\widehat{m}=\operatorname*{arg\,max}_{m\in\Omega}P(X_{i}^{t}=x_{i}^{t},Y_{i}^ {t}=Y_{j\in\mathbb{N}(i)}^{t+1}|I_{t}), \tag{4}\]  
where \(\widehat{m}\) is a set of occupancy maps and \(\Omega\) is the space of occupancy maps satisfying several constraints in (7) to (10). Assume the conditional independence of the occupancy maps given \(I^{t}\) is true and our objective function can be rewritten as follows based on log function (the detailed deduction process can be seen in the Appendix A of this paper):  
\[ \begin{split}\widehat{m}&=\operatorname*{arg\, max}_{x\in\Omega}\log\prod_{t,i}P(X_{i}^{t}=x_{i}^{t},Y_{i}^{t}=Y_{j\in \mathbb{N}(i)}^{t+1}|I_{t})\\ &=\operatorname*{arg\,max}_{x\in\Omega}\sum_{t=1}^{T}\sum_{i=1}^ {n}\log P(X_{i}^{t}=x_{i}^{t},Y_{i}^{t}=Y_{j\in\mathbb{N}(i)}^{t+1}|I_{t})\\ &=\operatorname*{arg\,max}_{x\in\Omega}\sum_{t=1}^{T}\sum_{i=1}^ {n}\left(\log\frac{\rho_{i}^{t}\cdot s_{i,j\in\mathbb{N}(i)}^{t}}{1-\rho_{i}^ {t}}\right)\cdot x_{i}^{t}.\end{split}  \tag{5}\]The \(x_{i}^{t}\) represents the actual occupancy of location \(i\) at time \(t\), and it is equal to the sum of flows leaving from the same location (\(\sum f_{i,j}^{t}\)). Therefore, together with the constraints, our goal is to solve the following linear program optimization problem:  
\[\max\ \sum_{t=1}^{T}\sum_{i=1}^{n}\left(\log\frac{\rho_{i}^{t}\cdot s_{ij,j\in \mathbb{N}(i)}^{t}}{1-\rho_{i}^{t}}\right)\cdot\sum_{j\in\mathbb{N}(i)}f_{i,j}^ {t} \tag{6}\]  
s.t.