Högskolan i Skövde

The increased societal need for surveillance and the decrease in cost of sensors have led to a number of new challenges. The problem is not to collect data but to use it effectively for decision support. Manual interpretation of huge amounts of data in real-time is not feasible; the operator of a surveillance system needs support to analyze and understand all incoming data. In this paper an approach to intelligent video surveillance is presented, with emphasis on finding behavioural anomalies. Two different anomaly detection methods are compared and combined. The results show that it is possible to best increase the total detection performance by combining two different anomaly detectors rather than employing them independently.

Abnormal behaviour may indicate important objects and events in a wide variety of domains. One such domain is intelligence and surveillance, where there is a clear trend towards more and more advanced sensor systems producing huge amounts of trajectory data from moving objects, such as people, vehicles, vessels and aircraft. In the maritime domain, for example, abnormal vessel behaviour, such as unexpected stops, deviations from standard routes, speeding, traffic direction violations etc., may indicate threats and dangers related to smuggling, sea drunkenness, collisions, grounding, hijacking, piracy etc. Timely detection of these relatively infrequent events, which is critical for enabling proactive measures, requires constant analysis of all trajectories; this is typically a great challenge to human analysts due to information overload, fatigue and inattention. In the Baltic Sea, for example, there are typically 3000–4000 commercial vessels present that are monitored by only a few human analysts. Thus, there is a need for automated detection of abnormal trajectory patterns. In this thesis, we investigate algorithms appropriate for automated detection of anomalous trajectories in surveillance applications. We identify and discuss some key theoretical properties of such algorithms, which have not been fully addressed in previous work: sequential anomaly detection in incomplete trajectories, continuous learning based on new data requiring no or limited human feedback, a minimum of parameters and a low and well calibrated false alarm rate. A number of algorithms based on statistical methods and nearest neighbour methods are proposed that address some or all of these key properties. In particular, a novel algorithm known as the Similarity-based Nearest Neighbour Conformal Anomaly Detector (SNN-CAD) is proposed. This algorithm is based on the theory of Conformal prediction and is unique in the sense that it addresses all of the key properties above. The proposed algorithms are evaluated on real world trajectory data sets, including vessel traffic data, which have been complemented with simulated anomalous data. The experiments demonstrate the type of anomalous behaviour that can be detected at a low overall alarm rate. Quantitative results for learning and classification performance of the algorithms are compared. In particular, results from reproduced experiments on public data sets show that SNN-CAD, combined with Hausdorff distance  for measuring dissimilarity between trajectories, achieves excellent classification performance without any parameter tuning. It is concluded that SNN-CAD, due to its general and parameter-light design, is applicable in virtually any anomaly detection application. Directions for future work include investigating sensitivity to noisy data, and investigating long-term learning strategies, which address issues related to changing behaviour patterns and increasing size and complexity of training data.

Human operators of modern surveillance systems are confronted with an increasing amount of trajectory data from moving objects, such as people, vehicles, vessels, and aircraft. A large majority of these trajectories reflect routine traffic and are uninteresting. Nevertheless, some objects are engaged in dangerous, illegal or otherwise interesting activities, which may manifest themselves as unusual and abnormal trajectories. These anomalous trajectories can be difficult to detect by human operators due to cognitive limitations.

In this thesis, we study algorithms for the automated detection of anomalous trajectories in surveillance applications. The main results and contributions of the thesis are two-fold. Firstly, we propose and discuss a novel approach for anomaly detection, called conformal anomaly detection, which is based on conformal prediction (Vovk et al.). In particular, we propose two general algorithms for anomaly detection: the conformal anomaly detector (CAD) and the computationally more efficient inductive conformal anomaly detector (ICAD). A key property of conformal anomaly detection, in contrast to previous methods, is that it provides a well-founded approach for the tuning of the anomaly threshold that can be directly related to the expected or desired alarm rate. Secondly, we propose and analyse two parameter-light algorithms for unsupervised online learning and sequential detection of anomalous trajectories based on CAD and ICAD: the sequential Hausdorff nearest neighbours conformal anomaly detector (SHNN-CAD) and the sequential sub-trajectory local outlier inductive conformal anomaly detector (SSTLO-ICAD), which is more sensitive to local anomalous sub-trajectories.

We implement the proposed algorithms and investigate their classification performance on a number of real and synthetic datasets from the video and maritime surveillance domains. The results show that SHNN-CAD achieves competitive classification performance with minimum parameter tuning on video trajectories. Moreover, we demonstrate that SSTLO-ICAD is able to accurately discriminate realistic anomalous vessel trajectories from normal background traffic.

This paper presents a novel application of the theory of conformal prediction for distribution-independent on-line learning and anomaly detection. We exploit the fact that conformal predictors give valid prediction sets at specified confidence levels under the relatively weak assumption that the (normal) training data together with (normal) observations to be predicted have been generated from the same distribution. If the actual observation is not included in the possibly empty prediction set, it is classified as anomalous at the corresponding significance level. Interpreting the significance level as an upper bound of the probability that a normal observation is mistakenly classified as anomalous, we can conveniently adjust the sensitivity to anomalies while controlling the rate of false alarms without having to find any application specific thresholds. The proposed method has been evaluated in the domain of sea surveillance using recorded data assumed to be normal. The validity of the prediction sets is justified by the empirical error rate which is just below the significance level. In addition, experiments with simulated anomalous data indicate that anomaly detection sensitivity is superior to that of two previously proposed methods.

Automated detection of anomalous trajectories is an important problem in the surveillance domain. Various algorithms based on learning of normal trajectory patterns have been proposed for this problem. Yet, these algorithms suffer from one or more of the following limitations: First, they are essentially designed for offline anomaly detection in databases. Second, they are insensitive to local sub-trajectory anomalies. Third, they involve tuning of many parameters and may suffer from high false alarm rates. The main contribution of this paper is the proposal and discussion of the Sliding Window Local Outlier Conformal Anomaly Detector (SWLO-CAD), which is an algorithm for online detection of local sub-trajectory anomalies. It is an instance of the previously proposed Conformal anomaly detector and, hence, operates online with well-calibrated false alarm rate. Moreover, SWLO-CAD is based on Local outlier factor, which is a previously proposed outlier measure that is sensitive to local anomalies. Thus, SWLO-CAD has a unique set of properties that address the issues above.

Abnormal behaviour may indicate important objects and situations in e.g. surveillance applications. This paper is concerned with algorithms for automated anomaly detection in trajectory data. Based on the theory of Conformal prediction, we propose the Similarity based Nearest Neighbour Conformal Anomaly Detector (SNN-CAD) which is a parameter-light algorithm for on-line learning and anomaly detection with wellcalibrated false alarm rate. The only design parameter in SNN-CAD is the dissimilarity measure. We propose two parameterfree dissimilarity measures based on Hausdorff distance for comparing multi-dimensional trajectories of arbitrary length. One of these measures is appropriate for sequential anomaly detection in incomplete trajectories. The proposed algorithms are evaluated using two public data sets. Results show that high sensitivity to labelled anomalies and low false alarm rate can be achieved without any parameter tuning.

This paper presents a first attempt to evaluate two previously proposed methods for statistical anomaly detection in sea traffic, namely the Gaussian Mixture Model (GMM) and the adaptive Kernel Density Estimator (KDE). A novel performance measure related to anomaly detection, together with an intermediate performance measure related to normalcy modeling, are proposed and evaluated using recorded AIS data of vessel traffic and

simulated anomalous trajectories. The normalcy modeling evaluation indicates that KDE more accurately captures finer details of normal data. Yet, results from anomaly detection show no significant difference between the two techniques and the performance of both is considered suboptimal. Part of the explanation is that the methods are based on a rather artificial division of data into geographical cells. The paper therefore discusses other clustering approaches based on more informed features of data and more background knowledge regarding the structure and natural classes of the data.