{'fraction_non_alphanumeric': 0.030065568527106987, 'fraction_numerical': 0.0051495282264513035, 'mean_word_length': 4.661053775122216, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Intelligent Querying for Target Tracking in Camera Networks using Deep Q-Learning with n-Step Bootstrapping

Surveillance camera networks are a useful infrastructure for various visual analytics applications, where high-level inferences and predictions could be made based on target tracking across the network. Most multi-camera tracking works focus on target re-identification and trajectory association problems to track the target. However, since camera networks can generate enormous amount of video data, inefficient schemes for making re-identification or trajectory association queries can incur prohibitively large computational requirements. In this paper, we address the problem of intelligent scheduling of re-identification queries in a multi-camera tracking setting. To this end, we formulate the target tracking problem in a camera network as an MDP and learn a reinforcement learning based policy that selects a camera for making a re-identification query. The proposed approach to camera selection does not assume the knowledge of the camera network topology but the resulting policy implicitly learns it. We have also shown that such a policy can be learnt directly from data. Using the NLPR MCT and the Duke MTMC multi-camera multi-target tracking benchmarks, we empirically show that the proposed approach substantially reduces the number of frames queried.


Introduction
Camera networks are becoming ubiquitous in smart cities where monitoring of urban environments has numerous applications like traffic management, law enforcement and security and automated surveillance. In these scenarios, camera sensors are deployed in public spaces like road intersections, common areas in residential, commercial and government complexes to collect data, which is transmitted, stored and analysed by the government or local authorities. For example, surveillance cameras in residential and commercial complexes can be used to identify and track trespassers and unauthorized personnel or for forensic analysis for investigating crimes.
For these applications, tracking targets is important and most approaches for multicamera tracking are driven by the state-of-the-art visual object detection, tracking motion. In our formulation, we have used one MDP for camera selection decision to enable single target tracking in multiple cameras which can easily be extended to tracking multiple targets by simultaneously running multiple policies. Deep-Q learning [2] has shown human level performance in playing Atari games using visual frames. Such methods use one-step reward during the training process, however, n-steps reward [35] can help in faster convergence by bootstrapping states for multi-step reward. Time limits [5] in reinforcement learning has shown that randomizing the state vector after a time limit achieves better performance. Recently, deep reinforcement learning techniques were applied for visual object detection [36] and tracking [31,37,38]. These approaches are applied for single object/target tracking in a single camera field-ofview. To our knowledge, we are the first to explore deep reinforcement learning for single target tracking in a camera network. We have shown that a policy learned using reinforcement learning can intelligently poll cameras to reduce the number of frames required for target's template matching. In our approach, we have used deep-Q learning [2] to learn a policy to poll a camera frame at any time-step to look for the presence of the target.

Proposed Methodology
In this section, we will provide the details of the system architecture and the reinforcement learning formulation for the camera selection decision problem. Figure 1 shows our system architecture, which consists of two blocks: First, block Q which learns a policy π to select the next camera where the target is likely to appear given target's current state. The second block verifies the presence of the target in the selected camera frame. In surveillance, this is usually done manually using human input or automatically using re-identification [26,25] based approaches. We will name this second block, the presence block. The presence block takes as input the selected camera frame and will return 1 if the target is present in the camera frame along with the corresponding bounding box location, otherwise it returns a 0. As our focus is on learning the policy for camera selection, we being with the assumption that the presence block is perfect, and then investigate the impact of error in presence prediction. We achieve this by using ground truth labels for simulating a perfect Re-Id approach, and then induce random matching errors at different levels, in effect simulating outputs from Re-Id models at different levels of accuracy. This setting is followed in order to systematically evaluate the strength of our camera selection policy.

System Overview
The block Q, takes as input the current state (detailed in next subsection) and selects a camera index which will be polled to search the target using the presence block.
The policy selects one of the N + 1 actions, where N is the number of cameras. The first N actions correspond to each camera and the N +1 th action is to be selected when the target is transitioning from one camera's FOV to another. The sequence of selected cameras gives the target's trajectory in terms of the cameras in which the target appears termporally. This is a non-trivial task due to the unknown and non-deterministic transition time of each target during camera transitions which also requires to correct any wrong selections made at previous timestamps. Consider the examples shown in Fig.   2, where the transition times between a pair of cameras are different for all targets. The policy is implemented using a neural network model depicted in Fig. 3. The network parameters are learned using deep Q-learning [2] with n-steps bootstrapping [35]. In the subsequent subsection, we will provide details of the training and testing algorithm for camera selection decisions.

Markov Decision Process and Q-learning
The goal of reinforcement learning is to learn a policy that decides sequential actions specific to the target's state by maximizing a cumulative reward function [35].
Our system architecture uses deep Q-learning to learn a policy to make camera selection decisions. A decision problem can be formulated using a Markov Decision Process (MDP). The MDP is defined by the tuple (S, A, f, R), where S the set of states, A is the set of actions, f a (s t , s t+1 ) is the state transition function and R(s, a) is the reward function that determines the reward that the environment provides by taking an action a ∈ A at state s ∈ S. In an MDP, we learn a stochastic policy to decide the probability of an action given the current state of the agent. The environment then responds at next time with the next state (decided by the state transition function) and a reward (decided by the reward function). In real-world, both the state-transition function and the reward function can be stochastic. Given the MDP formulation, we can learn the policy using trial-and-error strategy. Our MDP formulation is given in the later part of this subsection. We define a state-action value function Q to estimate the expected value of the return for taking action a in state s by Q(s, a). Return R t at time t is defined as the discounted sum of future rewards: Algorithm 1 Deep Q-network training procedure with n-step bootstrapping. π is the policy to make camera selection decisions. c,b is the initial location of the target with c as the current camera and b as the corresponding bounding box location. With probability ǫ, choose action c uniformly at random, and with probability 1 − ǫ, choose action using the policy in equation 5 8: bb ← getBoundingBox(c) ⊲ get the bounding box from presence block 9: if rand() < 0.5 then ⊲ random steps are taken for exploration 10: rsteps ← randint (20) 11: if bb is NOT EMPTY then⊲ update last seen observation vector if target is present in c 12: xt ← (c,bb) 13: τ ← ZERO 14: else 15: τ + = rsteps 16: h ← updateHistory(h,c) 17: s ′ ← f(xt, h, τ ) ⊲ observe the next state and reward 18: r ← getReward(s,c)

19:
Append transition (s, c, s ′ , r) to replay memory M, pop last element if overflow 20: if s ′ is terminal then break 21: s ← s ′

22:
Sample a random minibatch B from M

23:
For each sample (si, ai, s ′ i , ri) in minibatch, compute the n-step target yi = ri + γmaxaQ(s ′ i , a) ⊲ For brevity, target value is shown for 1-step reward 24: Update the Q-network using adam algorithm [39] on the minibatch and repeat until convergence 25: return π Where γ is the discount factor which is typically included to make the return bounded. The estimates will then be used to make the action selection decision. We use state-action value function Q π (s, a) to learn the expected return starting at state s and taking action a and using policy π for further time-steps (we will use Q(s, a) in place of Q π (s, a) for all following text). The value function will tell us the expectation of how good (in terms of reward) the current state and action will result in future given the current policy.
The goal is to learn the optimal state-action function Q * [35]. The optimal Qfunction Q * (s, a) can be learned using reinforcement learning techniques such as Qlearning, policy gradient, etc. We use Q-learning to learn an optimal Q-function because it is an off-policy and model-free algorithm i.e., an optimal policy can be learned by state-space exploration using trial-and-error and doesn't need an accurate state transition model. We have explained the learning procedure later in this subsection.
We formulate the camera selections as a decision problem where each camera is considered as a separate action. As noted by related works [29], the target tracking over a camera network can be NP-hard for searching the target in all cameras and at all times and therefore, this becomes important to reduce the number of search operations while tracking a target across the multiple cameras. Selecting one camera for the search operation will reduce the need for searching across all cameras. The cameras in a typical camera network are deployed far apart and hence searching is pointless when the target is transitioning between cameras. To ensure this the policy learns to decide a null camera when the target is not visible in any of the camera. Therefore, the task is to learn a policy π(s t ) at target's state s t which will give the probability of selecting a camera (equivalently selecting an action) given the current state i.e., p(a t |s t ), where a t is the action (or equivalently camera in the context of camera selection decisions). Such a policy can predict the period of visibility (when it is visible in any of the camera) of the target in the camera network, and the period of invisibility (when the target is not visible in any of the camera). We will show that this policy can be learned directly from data using the trial-and-error based approach i.e., by taking feedback from the environment.
However, this problem doesn't map to the MDP directly because of the target's partial observability like occlusion from other targets or the target not present in the selected camera. For example, if the policy selects camera c i but the target is present in the FOV of camera c j . The observation that the learning agent gets from the environment doesn't provide the target's state information and it makes the state non-Markov.
Hence, we need to create a state vector from the noisy observations which is Markov (next state is independent of the previous state, given the current state). For partial observable environment, we can keep a history vector of the observations starting from the initial location to the current time which helps to estimate the next state. However, considering full history length in the state vector becomes intractable. Therefore, we need to create state from history which is Markov. In addition to the observations, we keep the action history and time elapsed in the state vector. To read more about the partial observable problem, readers are encouraged to read [35]. The individual components of the state vector are defined in the following text: State transition function: After deciding an action a t at time t, the next state s t+1 is decided by following state evolution function: The function appends the one-hot encoding of the selected camera c t to the camera history vector. If the target is found in selected camera then last seen observation vector x t is updated by including new (c, b) otherwise τ is incremented by 1.

Reward:
The reward function r(s, a) is defined for each state and action a pair.
In [1], we provided a binary reward function and here we use a dense reward. During training, this reward helps in knowing how long will it take to end the current handover.
give At time t, it is following: Assumptions: We assume that all the cameras of the camera network are uniquely identifiable and the camera network topology doesn't change during testing phase (the CCTV network infrastructure doesn't frequently change in the real world too).
Policy: The policy π selects an optimal action from the learned Q-value functions.
After learning, given the target state, it selects an optimal action using the learned Qvalue function in-state s t as: Q-learning: Q-learning is a temporal-difference (TD) [35] learning algorithm which learns directly from state-space exploration without knowing a state-transition model.
The Q-learning learns an optimal Q-value function by iteratively updating the values using the following bellman equation independent of the policy being followed: Where α is the learning rate, and γ is the discount factor. At state s t , the learning agent performs an action a t and then the environment responds with a new state s t+1 and a reward value. An optimal Q-function should reflect the expected return for the state-action pair. Usually we start with a random policy and we explore the state-space by taking actions to update the value function about the goodness of the state-action pair. Sufficient exploration is essential for the Q-learning methods to update returns for a large number of state-action pair. In RL, we use epsilon-greedy exploration strategy [35]. The update value considers the reward received for next one-step only but the one-step reward doesn't give the actual future reward during initial steps and the policy will not learn the right camera handover for larger transition times. Hence we are incorporating n-step rewards [35] to update the value function.
Q-learning with n-step bootstrapping: The Q-learning update equation specified above updates the value function at next time using one step reward. In n-step reward, we update the value of a state after receiving rewards for n time steps. For example, taking n = 3, would change the Q-learning bellman equation 6 to: Neural network model: Our neural network model is shown in figure 3. For the neural network, we will find the optimal weights which will help the learning agent to get maximum reward. For the reward based learning, we have used deep Q learning [2] algorithm to update the neural network weights based on the reward received from  Training procedure: To train the network, we need to have the target labels corresponding to each input. Deep-Q learning [2] algorithm uses the return at each step as the target label. The output of the network at state s t is Q(s t , a t ) ∀a t ∈ A and the corresponding target is the discounted future reward for n-steps. For simplicity, taking n = 1, the target y t for state s t after receiving a reward r t+1 from environment is r t+1 + γmax a Q(s t+1 , a). We have used mean-square error to compute loss at each time-step. Hence, when action a i is taken at state s t , the loss (corresponding to action a i ) can be written as:

Camera Selection Decisions using Deep-Q Network
The loss term for actions other than a i will be zero (there are N + 1 actions). In RL, the term in brackets is also known as TD (Temporal Difference) error. In the loss for n-step bootstrapping, we replace the next (one) step reward with the n-step return.
The step by step training procedure is shown in algorithm 1.
Note that the training procedure is same irrespective of whether the target is inside a camera field-of-view or transitioning between cameras. For training the neural network, we initialized the state vector with the initial location of the target and history vector to all zeros. The selected action (camera index) is then used to verify the The second plot of the figure shows that the reward saturates at later training epochs.

Evaluation and Results
In this section, we present details of the datasets used, the evaluation metric and the experimental results of the proposed architecture on the used datasets.

Dataset and Evaluation Metric
Dataset: We have used NLPR MCT data set [3] and DukeMTMC [4] dataset to evaluate the proposed architecture for camera selections in multi-camera network for  The training and the testing sets are constructed from each datasets by randomly selecting half the people for the training and the remaining half for testing. However, the evaluation benchmark of DukeMTMC dataset doesn't provide platform for camera selection performance and hence to train the policy and to evaluate the performance, we have divided the available training set into two parts by splitting person identities in two sets. Therefore, for camera selection decisions, we are reporting performance on the sub-part of the actual training set. The two sets contain mutually exclusive person identities. We expect the policy to implicitly learn the network topology, and so long as the network is static, the policy should work for all new, unseen target individuals.
Typically, CCTV network topologies in the real-world are seldom modified.
We define evaluation metrics over the entire sequence of frames generated by the camera network. The sequence is indexed by time-steps corresponding to the time of frame capture for the cameras. Since the cameras operate on the same frame rate for a given subset, we can ignore any synchronization errors without any significant impact on the camera selection and tracking performance.
Evaluation Metric: To evaluate the camera selection performance, we report camera selection accuracy, precision and recall computed over the entire sequence of each subset. In order to consider instances when the target is not visible in any of the cameras, we introduce a dummy null camera and denote it by C × . Given a target, let the ground truth sequence of cameras in which it appears be contained in the vector g and sequence of cameras polled by the policy be in vector p with the i th element indicated using a subscript. The Accuracy (A), precision (P) and recall (R) are defined as following for a single target The final value for each of these metrics is reported as an average computed over all targets. Along with A, P, R, we also report number of frames polled (F ) during an inter-camera transition of the target. It is defined as F is an important measure because with a large number of frames polled, the chance of false alarms during a re-identification query as well as the computational complexity is substantially increased. We perform evaluation in two parts, one for ICT alone and another for ICT along with SCT. For ICT alone case, we do not consider the frames when the target was seen in a single camera field-of-view. We also evaluate the overall performance of target tracking in a camera network, when our camera selection policy is used for ICT. We use the standard Multi-Camera Tracking Accuracy (MCTA), which gives a single scalar value for all components involved in multi-camera tracking, i.e., F1-score for detection, number of target handovers for single camera tracking, and the number of handovers in inter-camera tracking. The metric is defined as where P T is the precision, R T is recall for target IDs. The number of target-ID mismatches at time t is given by µ t and tp t is the number of true positives in a single camera at time t. The superscripts s and c denote the single camera tracking (SCT) or cross-camera tracking (ICT) scenario. Readers are requested to see [4,3] for details about the MCTA metric.
We have proposed a single target tracking approach that tracks the given target across multiple cameras whereas the related approaches on the benchmark datasets are multi-target multi-camera. To make a fair comparison with related approaches, we have created a multi-target version of our algorithm. To compute multi-target tracking results, we are running multiple pipelines of our approach for multiple targets. In our approach, the tracking performance of one target does not depend on another and hence the approach can be easily extended to multi-target tracking problem.
Algorithm 2 Camera selection decisions using deep Q learning. s ← initialState(c, b, h, τ ) ⊲ Create initial state using history and location 4: while the video sequence ends do 5: c = argmax(π(s)) ⊲ Choose an action using the learned policy 6: Select a random c, if τ reaches the max time-limit 7: b ← get the bounding box location using presence block 8: if b is not empty then 9: Update xt ← (c,b) and τ ← ZERO τ + = 1 12: h ← updateHistory(h,c) ⊲ Update history at every time-step 13: s ← f (xt, h, τ ) ⊲ Observe next states 14: Append (c,b) to trajectory 15: return trajectory

Camera Selection Performance of the Learned Policy
In this subsection, we will describe the performance of the learned policy for camera selection decisions. There are two cases for tracking a target in a camera network.
First, ICT (Inter-Camera Tracking) where the task is to identify the correct camera handovers that the target performs. Second, is SCT+ICT (Single Camera Tracking + ICT) where the task is to identify the correct cameras when the target is moving in a single camera field-of-view along with the camera handovers. To perform the experiment, we have initialized the initial state of the target with its initial location with history vector being all zeros. At each time-step, the learned policy selects a camera index where the target is likely to be present. The selected camera is then queried to identify whether the target is present in the selected camera field-of-view. The presence of the target is used to locate its spatial location (bounding box) in the selected camera frame. For surveillance, this task is usually performed by human agents who continuously watch the camera feed. Alternatively, this task can be achieved by re-identification based methods to automatically identify the presence of the target. Such methods use visual template matching to re-identify an object in different camera feeds given the visual template of the target. To evaluate the camera selection decisions, we use correct presence of the target from the ground truth data. We make this simplifying choice in this experiment to eliminate the uncertainty introduced due to the re-identification performance. The policy continues polling of cameras until the target exits the camera network or the sequence terminates. The complete procedure Table 3: Table is showing camera selection accuracy (A), precision (P) and recall (R) for the proposed method and baseline approaches for NLPR dataset for the case of both ICT and SCT together. Metrics like accuracy, precision and recall encapsulate overall performances and allow comparative analysis as shown in Table 2, 3 and 4 which reports the camera selection performance on each dataset. Table 2 shows accuracy (A), precision (P), Table 4: Table is showing camera selection accuracy (A), precision (P) and recall (R) for the proposed method and baseline approaches for DukeMTMC dataset for both ICT alone and ICT-SCT together. The Gaussian approach is not defined for SCT+ICT case. In the table, OM signifies Out-of-Memory error.
ICT alone SCT + ICT  Table 3 shows A, P, R for NLPR MCT dataset for both SCT and ICT and Table 4 shows the camera selection decision performance for DukeMTMC dataset for both cases, ICT alone and SCT and ICT together.
In addition to the proposed policy's performance, we are comparing the camera selection performance of the policy with three baseline approaches used in related works.
The Exhaustive approach is a brute-force approach which polls each camera at all time steps until the target is found in one of the cameras. The table shows that it has 100% accuracy but poor precision. The Neighbor approach assumes that the camera network topology is known and searches the target by polling only in the neighboring cameras.
Approaches proposed in [10,23] searches the target in the adjacent cameras and hence process the same number of frames as the neighbor search approach. Along with these two approaches, we also compare camera selection performance with a method proposed in [24]. The approach proposed in [24] first estimates the distribution of the camera transitions assuming the fact that the multiple targets generally follow same paths and then samples a transition time to reduce the number of frames to be processed. They estimate a Gaussian distribution and hence we named this approach as Gaussian. After the transition time, they start searching the target in cameras using a camera link model which will link different cameras having a path for transition. We repeated their experiment by estimating a Gaussian distribution from the train set and sampling a transition time for each person in the test set. The camera link model is used as set of neighboring cameras. The metrics computed in each table are reported for two cases: For ICT, the metrics are computed using equation (9), but only using the time instances when the target is transitioning from one camera to the other. In case of SCT + ICT, the entire sequences are used. As expected, we see that the proposed policy has better precision than the other competing approaches. The Gaussian method is excluded in case of SCT + ICT, as the distribution is only defined for the ICT case.
While the A, P and R measures indicate the overall performance of camera selection, a confusion matrix shows the pairwise miss-classification in camera selection. Based on the cameras being polled by our policy at various time steps, we report a confusion matrix for DukeMTMC dataset as shown in Table 5. Our previous implementation in [1] using Q-learning goes out of memory for this dataset due to a very large state space. The confusion matrix is computed using deep learning based approximation of the Q-learning algorithm.  The figure reflects the performance of deep RL policy for making camera selection decisions. One important aspect of target tracking in multiple cameras is computational time. Many related methods match target template across neighboring cameras [10,23], all cameras [15,29] for offline tracking. However, such approach will require a large amount of frames to be processed for template matching. Using the proposed policy, this template matching will be limited to a single camera per time-step per person. In figure 7, we have compared the number of frames to be processed of various such approaches. The figure shows the boxplot of F -metric scores computed over all targets using the deep RL policy and various baseline approaches on DukeMTMC dataset. 8 cameras).

Impact of Camera Selection Decisions on Target Tracking in Camera Networks
Now we will show the effectiveness of the camera selection decisions to enable target tracking in a camera network. To complete the tracking pipeline, we simulate the presence block of our proposed architecture. To simulate the presence block errors in a typical re-identification pipeline are generated by wrongly identifying the target with other available objects. We will compare the performance with state-of-the-art tracking methods.
To perform this experiment, we have initialized the state vector with the initial lo-  The predicted trajectory is the sequence of (c,b) i.e., camera and bounding box values.
The predicted trajectory of the target is then used to compute the MCTA metric scores.
We have compared the performance of the policy with simulated re-identification errors with various state-of-the-art methods on the NLPR MCT dataset. The MCTA scores are shown in the tables 6 and 7 for ICT alone case and SCT+ICT case respectively.
In shows the overall performance of the various methods i.e., during both single-camera tracking (SCT) and inter-camera tracking (ICT). The same experiments are reported by the related methods on NLPR dataset. In comparison to other methods, our approach performs better in most cases at 0% error in re-identification. For higher errors, our method (especially deep RL) starts performing worse than others. Also, the related approaches are multi-target and multi-camera (MTMC) tracking approach whereas ours is single-target and multi-camera tracking. Therefore, to make a fair comparison, we have extended our approach to MTMC as explained in section 4.1. Similarly, results for DukeMTMC dataset are shown in the table 8.

Discussion
We have proposed an approach for intelligent camera selection for dealing with target handovers in multi-camera target tracking. Our initial work used exact RL methods [1] and extended it to approximate methods using Deep RL in order to deal with larger camera networks. The deep RL implementation make better camera selection decisions and can be used with larger camera networks. However, there are a few limitations of the proposed deep RL approach. First, the performance of deep RL approach is sensitive to errors in Re-id. This requires investigations in training the deep learning based policy with a real re-identification so that the policy can learn how to handle errors during tracking. Second, large transition times results in a policy that has heavily imbalanced action distributions, e.g., C x becoming the most frequent action.
Hence, efforts should be applied in exploring methods to handle imbalanced action space. Third, the indefinite transition time of a target makes exploration difficult in deciding whether the target goes out of the camera network or will appear again. There is a scope of improvement in identifying such cases.

Conclusion
We highlighted that re-identification queries in target tracking across camera networks can become a performance and computational bottleneck for practical systems.
We proposed a solution that intelligently makes these queries by selecting cameras that are more likely to contain the target at a given time. We proposed a reinforcement learning based approach that learns a policy for camera selection based on previous actions and target location. We empirically show on two benchmark datasets that the proposed approach substantially reduces the number of frames queried, with negligible loss of tracking performance.

Acknowledgement
We acknowledge Infosys Center for Artificial Intelligence (CAI) at IIIT-Delhi for its partial support for conducting this research work. [