# Multi-Player Tracking for Multi-View Sports Videos with Improved K-Shortest Path Algorithm
## 3 Methodology
### Existing KSP Tracking Method  
In fact, KSP (k-shortest path) was originally an algorithm for searching the \(k\) shortest path among all paths from the start point to the end point of a graph [9]. It can be applied to multiple object tracking which is formulated as a graph optimization problem for finding the shortest path in the graph determined by time and coordinates. In multiple-player tracking using KSP, it is assumed that each person moves one or more grid cells between successive frames in the tracking space of the world coordinate system which is divided into grids. Also, there is a restriction to only one person in each grid cell at most. The minimum cost flow problem that is originally regarded as an NP-hard integer programming problem can be relaxed to linear program problem by placing this constraint and it then becomes possible to solve in polynomial time.  
As shown in Figure 2, the network flow graph illustrates the principle of the tracking by KSP-based tracking methods. A node in location \(i\) at time \(t\) is represented as \(m_{i}^{t}\), where \(i\) denotes the location index and \(t\) is the time stamp. The linking edge \(e_{i,j}^{t}\) connects from node \(m_{i}^{t}\) to \(m_{j}^{t+1}\), which means a possible traveling route that a player can move between consecutive frames. The thick black lines in Figure 2 are possible links when the depth of the graph is assumed as 1, while the thin gray lines assume the depth of 2. It is clear to see that when the depth increases, the computing complexity will be multiplied as the possible links increase a lot. Similar to the granularity of the grid, the depth of the KSPs are determined in consideration of the moving speed of players and the frame rate. It is also noted that there are two virtual nodes, \(v_{\text{source}}\) and \(v_{\text{sink}}\), in the graph. These two special nodes are connected to all the possible nodes that player may enter and leave, which makes the KSP-based tracking system allow the players to enter and exit the tracking area.  
In the original KSP tracking method, the weight of the linking edge is determined by player occupancy probability at each position, while the linking weights outgoing from the virtual source node are set to zero. However, as the linking weights outgoing from node \(m_{i}^{t}\) only depend on the player occupancy probability at this node, the weights from \(m_{i}^{t}\) to any \(m_{j}^{t+1}\) are set as the same, even they belongs to different teams. In this case, when players come close to each other at time \(t\), their identities would be easily switched. In this paper, we rethink the linking weights by considering the identity information of the nodes. First, we need to construct an appearance model based on the existing player occupancy map. Then, we introduce similarity measurement between two nodes to calculate new linking weights. Ideally, when all of the identity cues for each node that might be occupied by a player  
Figure 2: The pipline of the multiple-player tracking system based on the KSP-AF tracking method mainly consists of three parts: (1) 3D player detection [42], (2) feature extraction, and (3) tracking by k-shortest paths with appearance feature (KSP-AF). The input of the whole system is multi-view basketball videos, and the output is multiple player trajectories. For the KSP-AF tracking, the inputs are both of the 3D detections represented as POM data and the extracted features for each detection.  
can be available, the obtained trajectories would be perfect without any identity switches. However, due to the serious occlusions in team sports, only a few pieces of identity information can be accessed. In this paper we further carry out extensive experiments to quantify the requirements of appearance features in KSP-based tracking.