{'fraction_non_alphanumeric': 0.03290866082914886, 'fraction_numerical': 0.008880773540274722, 'mean_word_length': 4.796968968005773, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Online Anomaly Detection in Surveillance Videos with Asymptotic Bounds on False Alarm Rate

Anomaly detection in surveillance videos is attracting an increasing amount of attention. Despite the competitive performance of recent methods, they lack theoretical performance analysis, particularly due to the complex deep neural network architectures used in decision making. Additionally, online decision making is an important but mostly neglected factor in this domain. Much of the existing methods that claim to be online, depend on batch or offline processing in practice. Motivated by these research gaps, we propose an online anomaly detection method in surveillance videos with asymptotic bounds on the false alarm rate, which in turn provides a clear procedure for selecting a proper decision threshold that satisfies the desired false alarm rate. Our proposed algorithm consists of a multi-objective deep learning module along with a statistical anomaly detection module, and its effectiveness is demonstrated on several publicly available data sets where we outperform the state-of-the-art algorithms. All codes are available at https://github.com/kevaldoshi17/Prediction-based-Video-Anomaly-Detection-.


Introduction
The rapid advancements in the technology of closed-circuit television (CCTV) cameras and their underlying infrastructural components such as network, storage, and processing hardware have led to a sheer number of surveillance cameras implemented all over the world, and estimated to go beyond 1 billion globally, by the end of the year 2021 [1]. Video surveillance is an essential tool used in law enforcement, transportation, environmental monitoring, etc. mainly for improving security and public safety. For example, it has become an inseparable part of crime deterrence and investigation, traffic violation detection, and traffic management. However, considering the massive amounts of videos generated in real-time, manual video analysis by human operator becomes inefficient, expensive, and nearly impossible, which in turn makes a great demand for automated and intelligent methods for analyzing and retrieving important information from videos, in order to maximize the benefits of CCTV.
One of the most important, challenging and time-critical tasks in automated video surveillance is the detection of abnormal events such as traffic accidents and violations, crimes, and natural disasters. Hence, video anomaly detection has become an important research problem in the recent years. Anomaly detection in general is a vast, crucial, and challenging research topic, which deals with the identification of data instances deviating from nominal patterns. It has a wide range of applications, e.g., in medical health care [2], cyber-security [3], hardware security [4], aviation [5], and spacecraft monitoring [6].
Given the important role that video anomaly detection can play in ensuring safety, security and sometimes prevention of potential catastrophes, one of the main outcomes of a video anomaly detection system is the real-time decision making capability. Events such as traffic accidents, robbery, and fire in remote places require immediate counteractions to be taken in a timely manner, which can be facilitated by the real-time detection of anomalous events. Despite its importance, a very limited body of research has focused on online and real-time detection methods. Moreover, some of the methods that claim to be online heavily depend on batch processing of long video segments. For example, [7] performs a normalization step which requires the entire video.
A vast majority of the recent state-of-the-art video anomaly detection methods depend on complex neural network architectures [8]. Although deep neural networks provide superior performance on various machine learning and computer vision tasks, such as object detection [9], image classification [10], playing games [11], image synthesis [12], etc., where sufficiently large and inclusive data sets are available to train on, there is also a significant debate on their shortcomings in terms of interpretability, analyzability, and reliability of their decisions [13].
For example, [14,15] propose using a nearest neighbor-based approach together with deep neural network structures to achieve robustness, interpretability for the decisions made by the model, and as defense against adversarial attack.
Additionally, to the best of the our knowledge, none of the neural network-based video anomaly detection methods has been analyzed in terms of performance guarantees. On the other hand, statistical and nearest neighbor-based methods remain popular due to their appealing characteristics such as being amenable to performance analysis, computational efficiency, and robustness [16,17].
Motivated by the aforementioned domain challenges and research gaps, we propose a hybrid use of neural networks and statistical k nearest neighbor (kNN) decision approach for finding anomalies in video in an online fashion. In summary, our contributions in this paper are as follows: • We propose a novel framework composed of deep learning-based feature extraction from video frames, and a statistical sequential anomaly detection algorithm.
• We derive an asymptotic bound on the false alarm rate of our detection algorithm, and propose a technique for selecting a proper threshold which satisfies the desired false alarm rate.
• We extensively evaluate our proposed framework on publicly available video anomaly detection data sets.
The remainder of the paper is organized as: Related Work (Section 2), Proposed Method (Section 3), Experiments (Section 4), and Conclusion (Section 5).

Related Work
Semi-supervised detection of anomalies in videos, also known as outlier detection, is a commonly adopted learning technique due to the inherent limitations in availability of annotated and anomalous instances. This category of learning methods deals with learning a notion of normality from nominal training videos, and attempts to detect deviations from the learned normality notion. [18,19].
There are also several supervised detection methods, which train on both nominal and anomalous videos. The main drawback of such methods is the difficulty in finding frame-level labeled, representative, and inclusive anomaly instances. To this end, [8] proposes using a deep multiple instance learning (MIL) approach to train on video-level annotated videos, in a weakly supervised manner. Although training on anomalous videos would enhance the detection capability on similar anomaly events, supervised methods typically suffer from unknown and novel anomaly types.
One of the key components of the video anomaly detection algorithms is the extraction of meaningful features, which can capture the difference between the nominal and anomalous events within the video. The selection of feature types has a significant impact on the identifiability of types of anomalous events in the video sequences. Many early video anomaly detection techniques and some recent ones focused on the trajectory features [20], which limits their applicability to the detection of the anomalies related to the trajectory patterns, and moving objects. For instance, [21] studied detection of abnormal vehicle trajectories such as illegal U-turn. [22] extracts human skeleton trajectory patterns, and hence is limited to only the detection of abnormalities in human behavior.
Motion and appearance features are another class of widely used features in this domain. [23] extracts motion direction and magnitudes, to detect spatio-temporal anomalies. Histogram of optical flow [24,25], and histogram of oriented gradients [26] are some other commonly used hand-crafted feature extraction techniques used in the literature. Sparse coding based methods [27] are also applied in detection of video anomalies. They learn a dictionary of normal sparse events, and attempt to detect anomalies based on the reconstructability of video from the dictionary atoms. [28] uses sparse reconstruction to learn joint trajectory representations of multiple objects.
In contrary to the hand-crafted feature extraction, are the neural network based feature learning methods. [29] learns the appearance and motion features by deep neural networks. [30] utilizes Convolutional Neural Networks (CNN), and Convolutional Long Short Term Memory (CLSTM) to learn appearance and motion features, respectively. Neural network based approaches have been recently dominating the literature. For example, [31] trains Generative Adversarial Network (GAN) on normal video frames, to generate internal scene representations (appearance and motion), based on a given frame and its optical flow, and detects deviation of the GAN output from the normal data, by AlexNet [10]. [32] trains a GAN-like adversarial network, in which a reconstruction component learns to reconstruct the normal test frames, and attempts to train a discriminator by gradually injecting anomalies to it, while concurrently the discriminator (detector) learns to detect the anomalies injected by the reconstructor. In [33,34], a transfer learning based approach is used for continual learning for anomaly detection in surveillance videos from a few samples.

Motivation
Anomaly detection in surveillance videos is defined as the identification of unusual events which do not conform to the expectation. We base our study on two important requirements that a successful video anomaly detector should satisfy: (i) extract meaningful features which can be utilized to distinguish nominal and anomalous data; and (ii) provide a decision making strategy which this is the first work to present theoretical performance analysis for a deep learning-based video anomaly detection method. Our MONAD framework is described in detail in the following sections.

Feature Selection
Most existing works focus on a certain aspect of the video such as optical flow, gradient loss or intensity loss. This in turn restrains the existing algorithms to a certain form of anomalous event which is manifested in the considered video aspect. However, in general, the type of anomaly is broad and unknown while training the algorithm. For example, an anomalous event can be justified on the basis of appearance (a person carrying a gun), motion (two people fighting) or location (a person walking on the roadway). To account for all such cases, The weights w 1 , w 2 , w 3 are used to adjust the relative importance of each feature category.

Frame Prediction
A heuristic approach for detecting anomalies in videos is by predicting the future video frame X t using previous video frames {X 1 , X 2 , . . . , X t−1 }, and then comparing it to X t through mean squared error (MSE). Instead of deciding directly on MSE, we use MSE of video frame prediction to obtain motion features (Section 3.5). GANs are known to be successful in generating realistic images and videos. However, regular GANs might face the vanishing gradient problem during learning as they hypothesize the discriminator as a classifier with the sigmoid cross entropy loss function. To overcome this problem, we use a modified version of GAN called Least Square GAN (LS-GAN) [35]. The GAN architecture comprises of a generator network G and a discriminator network D, where the function of G is to generate frames that would be difficult-to-classify by D.
Ideally, once G is well trained, D cannot predict better than chance. Similar to [7], we employ a U-Net [36] based network for G and a patch discriminator for D.
For training the generator G, we follow [7], and combine the constraints on intensity, gradient difference, optical flow, and adversarial training to get the following objective function where γ int , γ gd , γ of , γ adv ≥ 0 are the corresponding weights for the losses.
Intensity loss is the l 1 or l 2 distance between the predicted frame X and the actual frame X, which is used to maintain similarity between pixels in the RGB space, and given by Gradient difference loss is used to sharpen the image prediction and is given by where (i, j) denotes the spatial index of a video frame.
Optical flow loss is used to improve the coherence of motion in the predicted frame, and is given by where f is a pretrained CNN-based function called Flownet, and is used to estimate the optical flow.
Adversarial generator loss is minimized to confuse D as much as possible such that it cannot discriminate the generated predictions, and is given by where D( X i,j ) = 1 denotes "real" decision by D for patch (i, j), D( X i,j ) = 0 denotes "fake" decision, and L M SE is the mean squared error function.

Object Detection
We propose to detect objects using a real-time object detection system such as You Only Look Once (YOLO) [37] to obtain location and appearance features (Section 3.5). The advantage of YOLO is that it is capable of processing higher frames per second on a GPU while providing the same or even better accuracy as compared to the other state-of-the-art models such as SSD and ResNet. Speed is a critical factor for online anomaly detection, so we currently prefer YOLOv3 in our implementations. For each detected object in image X t , we get a bounding box (location) along with the class probabilities (appearance). As shown in Fig.   2, we monitor the center of the bounding boxes to track paths different objects might take in the training videos. Instead of simply using the entire bounding box, we monitor the center of the box and its area to obtain location features.
This not only reduces the complexity, but also effectively avoids false positives in case the bounding box is not tight. In a testing video, objects diverging from the nominal paths and class probabilities will help us detect anomalies, as explained in Section 3.6.

Feature Vector
Finally, for each object i detected in a frame, we construct a feature vector as: where M SE(X t , X t ) is the prediction error from the GAN-based frame predic- Hence, at any given time t, with n denoting the number of possible classes, the dimensionality of F i t is given by m = n + 4.

Anomaly Detection
Our goal here is to detect anomalies in streaming videos with minimal detection delays while satisfying a desired false alarm rate. We can safely hypothesize that any anomalous event would persist for an unknown period of time. This makes the problem suitable for a sequential anomaly detection framework [38].
However, since we have no prior knowledge about the anomalous event that might occur in a video, parametric algorithms which require probabilistic model and data for both nominal and anomaly cannot be used directly. Next, we explain the training and testing of our proposed nonparametric sequential anomaly detection algorithm. bound (φ) for δ t , given by Eq. (7), which is then used for selecting a threshold h, as explained in Section 3.7.
Testing: During the testing phase, for each object i detected at time t, the deep learning module constructs the feature vector F i t and computes the kNN (Euclidean) distance d i t with respect to the training instances in F M2 . The proposed sequential anomaly detection system then computes the instantaneous frame-level anomaly evidence δ t : where m is the dimensionality of feature vector F i t . Finally, following a CUSUMlike procedure [38] we update the running decision statistic s t as s t = max{s t−1 + δ t , 0}, s 0 = 0.
For nominal data, δ t typically gets negative values, hence the decision statistic s t hovers around zero; whereas for anomalous data δ t is expected to take positive values, and successive positive values of δ t will make s t grow. We decide that a video frame is anomalous if the decision statistic s t exceeds the threshold h.
After s t exceeds h, we perform some fine tuning to better label video frames as nominal or anomalous. Specifically, we find the frame s t started to grow, i.e., the last time s t = 0 before detection, say τ start . Then, we also determine the frame s t stops increasing and keeps decreasing for n, e.g., 5, consecutive frames, say τ end . Finally, we label the frames between τ start and τ end as anomalous, and continue testing for new anomalies with frame τ end + 1 by resetting s τ end = 0.

Threshold Selection
If the test statistic crosses the threshold when there is no anomaly, this event is called a false alarm. Existing works consider the decision threshold as a design parameter, and do not provide any analytical procedure for choosing its value.
For an anomaly detection algorithm to be implemented in a practical setting, a clear procedure is necessary for selecting the decision threshold such that it satisfies a desired false alarm rate. The reliability of an algorithm in terms of false alarm rate is crucial for minimizing human involvement. To provide such a performance guarantee for the false alarm rate, we derive an asymptotic upper bound on the average false alarm rate of the proposed algorithm.
Theorem 1. The false alarm rate of the proposed algorithm is asymptotically where h is the decision threshold, and ω 0 > 0 is given by

Datasets
We evaluate our proposed method on three publicly available video anomaly data sets, namely the CUHK avenue dataset [39], the UCSD pedestrian dataset [40], and the ShanghaiTech [41]

Implementation Details
In the prediction pipeline, the U-NET based generator and the patch discriminator are implemented in Tensorflow. Each frame is resized to 256 x 256 and normalized to [-1,1]. The window size t is set to 4. Similar to [7], we use the Adam optimizer for training and set the learning rate to 0.0001 and 0.00001 for the generator and discriminator, respectively. The object detector used is YOLOv3 which is based on the Darknet architecture and is pretrained on the MS-COCO dataset. During training, we extract the bounds which have a confidence level greater than 0.6, and for testing we consider confidence levels greater than or equal to 0.4. The weights w 1 , w 2 and w 3 are set to 1, 0.4 and 0.9 respectively. The sequential anomaly detection algorithm is implemented in Python.

Impact of Sequential Anomaly Detection
To demonstrate the importance of sequential anomaly detection in videos, we implement a nonsequential version of our algorithm by applying a threshold to the instantaneous anomaly evidence δ t , given in (7), which is similar to the approach employed by many recent works [7,8,19]. As Figure 3 shows, instantaneous anomaly evidence is more prone to false alarms than the sequential MONAD statistic since it only considers the noisy evidence available at the current time to decide. Whereas, the proposed sequential statistic handles noisy evidence by integrating recent evidence over time.

Results
We compare our results to a wide range of methods in Table 1. Recently, [19] showed significant gains over the rest of the methods. However, their methodology of computing the AuROC gives them an unfair advantage as they calculate the AuROC for each video in a dataset, and then average them as the AuROC of the dataset, as opposed to the other works which concatenate all the videos first and then determine the AuROC as the dataset's score.
As shown in Table 1 we are able to outperform the existing results in the avenue and UCSD dataset, and achieve competitive performance in the ShanghaiTech dataset. We should note here that our reported result in the ShanghaiTech dataset is based on online decision making without seeing future video frames. A common technique used by several recent works [7,19] is to normalize the computed statistic for each test video independently, including the ShanghaiTech dataset. However, this methodology cannot be implemented in an Hence, we also compare our online method with the online version of stateof-the-art method [7]. In that version, the minimum and maximum values of decision statistic is obtained from the training data and used for all videos in the test data to normalize the decision statistic, instead of the minimum and maximum values in each test video separately. AuROC value, which is the most common performance metric in the literature, considers the entire range (0, 1) of false alarm rates. However, in practice, false alarm rate must satisfy an acceptable level (e.g., up to 10%). In Figure 4, on the UCSD and ShanghaiTech data sets, we compare our algorithm with the online version of [7] within a practical range of false alarm in terms of the ROC curve (true positive rate vs. false positive rate). As clearly seen in the figures, the proposed MONAD algorithm achieves much higher true alarm rates than [7] in both datasets while satisfying practical false alarm rates.

Conclusion
For video anomaly detection, we presented an online algorithm, called MONAD, which consists of a deep learning-based feature extraction module and a statistical decision making module. The first module is a novel feature extraction technique that combines GAN-based frame prediction and a lightweight object detector. The second module is a sequential anomaly detector, which enables performance analysis. The asymptotic false alarm rate of MONAD is analyzed, and a practical procedure is provided for selecting its detection threshold to satisfy a desired false alarm rate. Through real data experiments, MONAD is shown to outperform the state-of-the-art methods, and yield false alarm rates consistent with the derived asymptotic bounds. For future work, we plan to focus on the importance of timely detection in video [49] by proposing a new metric based on the average delay and precision.

Acknowledgements
This research is funded in part by the Florida Center for Cybersecurity and in part by the U.S. National Science Foundation under the grant #2029875.
Appendix A. Proof of Theorem 1 In [38][page 177], for CUSUM-like algorithms with independent increments, such as MONAD with independent δ t , a lower bound on the average false alarm period is given as follows where h is the detection threshold, and ω 0 ≥ 0 is the solution to E[e ω0δt ] = 1.
To analyze the false alarm period, we need to consider the nominal case.
In that case, since there is no anomalous object at each time t, the selection of object with maximum kNN distance in δ t = (max i {d i t }) m − d m α does not necessarily depend on the previous selections due to lack of an anomaly which could correlate the selections. Hence, in the nominal case, it is safe to assume that δ t is independent over time.
We firstly derive the asymptotic distribution of the frame-level anomaly evidence δ t in the absence of anomalies. Its cumulative distribution function is given by It is sufficient to find the probability distribution of (max i {d i t }) m , the mth power of the maximum kNN distance among objects detected at time t. As discussed above, choosing the object with maximum distance in the absence of anomaly yields independent m-dimensional instances {F t } over time, which form a Poisson point process. The nearest neighbor (k = 1) distribution for a Poisson point process is given by where Λ(b(F t , r)) is the arrival intensity (i.e., Poisson rate measure) in the m-dimensional hypersphere b(F t , r) centered at F t with radius r [50]. Asymptotically, for a large number of training instances as M 2 → ∞, under the null (nominal) hypothesis, the nearest neighbor distance max i {d i t } of F t takes small values, defining an infinitesimal hyperball with homogeneous intensity λ = 1 around F t . Since for a homogeneous Poisson process the intensity is written as Λ(b(F t , r)) = λ|b(F t , r)| [50], where |b(F t , r)| = π m/2 Γ(m/2+1) r m = v m r m is the Lebesgue measure (i.e., m-dimensional volume) of the hyperball b(F t , r), we rewrite the nearest neighbor distribution as where v m = π m/2 Γ(m/2+1) is the constant for the m-dimensional Lebesgue measure. Now, applying a change of variables we can write the probability density of Finally, since the false alarm rate (i.e., frequency) is the inverse of false alarm period E ∞ [T ], we have where h is the detection threshold, and ω 0 is given above.