Piotr Bilinski
email: piotr.bilinski@inria.fr

Francois Bremond
email: francois.bremond@inria.fr

Human Violence Recognition and Detection in Surveillance Videos

In this paper, we focus on the important topic of violence recognition and detection in surveillance videos. Our goal is to determine if a violence occurs in a video (recognition) and when it happens (detection). Firstly, we propose an extension of the Improved Fisher Vectors (IFV) for videos, which allows to represent a video using both local features and their spatio-temporal positions. Then, we study the popular sliding window approach for violence detection, and we re-formulate the Improved Fisher Vectors and use the summed area table data structure to speed up the approach. We present an extensive evaluation, comparison and analysis of the proposed improvements on 4 state-ofthe-art datasets. We show that the proposed improvements make the violence recognition more accurate (as compared to the standard IFV, IFV with spatio-temporal grid, and other state-of-the-art methods) and make the violence detection significantly faster.

Introduction

Video surveillance cameras are part of our lives. They are used almost everywhere, e.g. at streets, subways, train and bus stations, airports, and sport stadiums. Today's increase in threats to security in cities and towns around the world makes the use of video cameras to monitor people necessary. The attacks on humans, fights, and vandalism are just some cases where detection, particularly violence detection, systems are needed.

In this paper, we focus on the important topic of violence recognition and detection in surveillance videos. Our goal is to determine if a violence occurs in a video (recognition) and when it happens (detection).

Over the last years, several violence recognition and detection techniques have been proposed. [START_REF] Datta | Person-on-Person Violence Detection in Video Data[END_REF] have used motion trajectory information and orientation information of person's limbs for person-on-person fight detection. One of the main drawbacks of this approach is that it requires precise segmentation, which is very difficult to obtain in real world videos. Instead, [START_REF] De Souza | Violence Detection in Video Using Spatio-Temporal Features[END_REF][START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF][START_REF] Mohammadi | Violence detection in crowded scenes using substantial derivative[END_REF][START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] have focused on local features and the bag-of-features approach; the main difference between these techniques lies in the type of features used. [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] have applied the STIP and SIFT, and [START_REF] De Souza | Violence Detection in Video Using Spatio-Temporal Features[END_REF] have used the STIP and MoSIFT features. [START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF] have proposed the VIolence Flows descriptor, encoding how flow-vector magnitudes change over time. [START_REF] Mohammadi | Violence detection in crowded scenes using substantial derivative[END_REF] have proposed a video descriptor based on substantial derivative. Despite recent improvements in violence recognition and detection, effective solutions for real-world situations are still unavailable.

The Improved Fisher Vectors (IFV) [START_REF] Perronnin | Improving the Fisher Kernel for Large-Scale Image Classification[END_REF] is a bag-offeatures-like video encoding strategy which has shown to outperform the standard bag-of-features. It is a video (and image) descriptor obtained by pooling local features into a global representation. It describes local features by their deviation from the "universal" generative Gaussian Mixture Model. The IFV has been widely applied for recognition tasks in videos [START_REF] Bilinski | Video Covariance Matrix Logarithm for Human Action Recognition in Videos[END_REF][START_REF] Bilinski | Representing Visual Appearance by Video Brownian Covariance Descriptor for Human Action Recognition[END_REF][START_REF] Kantorov | Efficient feature extraction, encoding and classification for action recognition[END_REF][START_REF] Wang | Action Recognition with Improved Trajectories[END_REF][START_REF] Wang | Action Recognition with Trajectory-Pooled Deep-Convolutional Descriptors[END_REF]. One of the main drawbacks of the IFV is that it simplifies the structure of a video assuming conditional independence across spatial and temporal domains; it computes global statistics of local features only, ignoring spatio-temporal positions of features.

Clearly, spatial information may contain useful information. A common way to use spatio-temporal information with IFV is to use either spatio-temporal grids [START_REF] Laptev | Learning realistic human actions from movies[END_REF] or multi-scale pyramids [START_REF] Lazebnik | Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories[END_REF]; however, these methods are still limited in terms of a detailed description providing only a coarse representation. There are several other state-of-theart methods [START_REF] Krapac | Modeling Spatial Layout with Fisher Vectors for Image Categorization[END_REF][START_REF] Krapac | Spatial Fisher Vectors for Image Categorization[END_REF][START_REF] Mccann | Spatially Local Coding for Object Recognition[END_REF][START_REF] Sanchez | Modeling the Spatial Layout of Images Beyond Spatial Pyramids[END_REF], but as they were proposed for images (for image categorization and object recognition), they cannot be directly applied for videos; moreover, [START_REF] Krapac | Modeling Spatial Layout with Fisher Vectors for Image Categorization[END_REF][START_REF] Krapac | Spatial Fisher Vectors for Image Categorization[END_REF] achieve similar results as compared to the spatial grids/pyramids, and [START_REF] Mccann | Spatially Local Coding for Object Recognition[END_REF] is parameter sensitive and requires additional parameter learning.

As opposed to the existing violence recognition and detection methods (which focus mainly on new descriptors), we focus on a video representation model due to two reasons: to make it more accurate for violence recognition, and to make it faster for violence detection. Firstly, we propose an extension of the IFV for videos (Sec. which allows to use spatio-temporal positions of features with the IFV. The proposed extension boosts the IFV and achieves better or similar accuracy (keeping the representation more compact) as compared to the spatio-temporal grids. Then, we study and evaluate the popular sliding window approach [START_REF] Klaser | Human Focused Action Localization in Video[END_REF] for violence detection. We re-formulate the IFV and use the summed area table data structure to speed up the sliding window method (Sec. 2.3). Then, we present an extensive evaluation, comparison and analysis of the proposed improvements on 4 state-of-the-art datasets (Sec. 3 and Sec. 4). Finally, we conclude in Sec. 5. Abnormal behavior detection: There are several methods for abnormal behavior and anomaly detection [START_REF] Cui | Abnormal Detection Using Interaction Energy Potentials[END_REF][START_REF] Mahadevan | Anomaly Detection in Crowded Scenes[END_REF][START_REF] Mehran | Abnormal Crowd Behavior Detection using Social Force Model[END_REF][START_REF] Mousavi | Analyzing Tracklets for the Detection of Abnormal Crowd Behavior[END_REF]. However, abnormalities do not represent a compact and well defined concept. Abnormality detection is a different research topic, with different constraints and assumptions, and therefore we do not focus on these techniques.

Boosting the Improved Fisher Vectors (IFV)

2.1. State-of-The-Art: Improved Fisher Vectors

This section provides a brief description of the Improved Fisher Vectors, introduced in [START_REF] Perronnin | Improving the Fisher Kernel for Large-Scale Image Classification[END_REF]. The mathematical notations and formulas provided here are in accordance with [START_REF] Perronnin | Improving the Fisher Kernel for Large-Scale Image Classification[END_REF], and we refer to it for more details.

Let X = {x t , t = 1 . . . T } be a set of T local features extracted from a video, where each local feature is of dimension D, x t ∈ R D . Let λ = {w i , µ i , Σ i , i = 1 . . . K} be parameters of a Gaussian Mixture Model (GMM): u λ (x) = K i=1 w i u i (x) fitting the distribution of local features, where w i ∈ R, µ i ∈ R D and Σ i ∈ R D×D are respectively the mixture weight, mean vector and covariance matrix of the i-th Gaussian u i . We assume that the covariance matrices are diagonal and we denote by σ 2 i the variance vector, i.e. Σ i = diag(σ 2 i ), σ 2 i ∈ R D . Moreover, let γ t (i) be the soft assignment of a descriptor x t to a Gaussian i:

γ t (i) = w i u i (x t ) K j=1 w j u j (x t ) , (1)
and let G X µ,i (resp. G X σ,i ) be the gradient w.r.t. the mean µ i (resp. standard deviation σ i ) of a Gaussian i:

G X µ,i = 1 T √ w i T t=1 γ t (i) x t -µ i σ i , (2)
G X σ,i = 1 T √ 2w i T t=1 γ t (i) (x t -µ i ) 2 σ 2 i -1 , (3)
where the division between vectors is as a term-by-term operation. Then, the gradient vector G X λ is the concatenation of all the K gradient vectors G X µ,i ∈ R D and all the K gradient vectors G X σ,i ∈ R D , i = 1 . . . K:

G X λ = [ G X µ,1 , G X σ,1 , . . . , G X µ,K , G X σ,K ] . (4)
The IFV (Improved Fisher Vectors) representation Φ X λ , Φ X λ ∈ R 2DK , is the gradient vector G X λ normalized by the power normalization and then the L2 norm:

Φ X λ = [ G X µ,1 , G X σ,1 , . . . , G X µ,K , G X σ,K ] √ +l2 . (5)
2.2. Boosting the IFV with spatio-temporal inf.

The Improved Fisher Vectors encoding simplifies the structure of a video assuming conditional independence across spatial and temporal domains (see Sec. 2.1). It computes global statistics of local features only, ignoring spatiotemporal positions of features. Thus, we propose an extension of the Improved Fisher Vectors which incorporates spatio-temporal positions of features into the video model.

Firstly, we represent positions of local features in a video normalized manner. In this paper, we focus on local trajectories only; however, the following representation can also be applied to spatio-temporal interest points [START_REF] Dollar | Behavior Recognition via Sparse Spatio-Temporal Features[END_REF][START_REF] Laptev | On Space-Time Interest Points[END_REF][START_REF] Willems | An Efficient Dense and Scale-Invariant Spatio-Temporal Interest Point Detector[END_REF] (with assumptions:

p t = (a t,1 , b t,1 , c t,1
) is the spatiotemporal position of a point and n t = 1).

Let P = {p t , t = 1 . . . T } be a set of T trajectories extracted from a video sequence and p t = ((a t,1 , b t,1 , c t,1 ), . . . , (a t,nt , b t,nt , c t,nt )) is a sample trajectory, where a feature point detected at a spatial position (a t,1 , b t,1 ) in a frame c t,1 is tracked in n t ≥ 1 subsequent frames until a spatial position (a t,nt , b t,nt ) in a frame c t,nt . We define the video normalized position pt of a center of a trajectory p t as:

pt = 1 v w n t nt i=1 a t,i , 1 v h n t nt i=1 b t,i , 1 v l n t nt i=1 c t,i , (6)
where v w is the video width (with the units in pixels), v h is the video height (in pixels), and v l is the video length (number of frames). We normalize the position of a center of a trajectory, so that the video size does not significantly change the magnitude of the feature position vector.

Once positions of local features are represented in a video normalized manner, we also consider using the unity based normalization to reduce the influence of motionless regions at the boundaries of a video, so that the large motionless regions do not significantly change the magnitude of the feature position vector. Let pt,i be the i-th dimension of the vector pt and min(p :,i ) (resp. max(p :,i )) be the minimum (resp. maximum) value of the i-th dimension among all the video normalized position vectors extracted from the training videos. When the condition ∀i : min(p :,i ) = max(p :,i ) is true, we can apply the unity based normalization to calculate the vector pt . The i-th dimension of the vector pt is:

pt,i = pt,i -min(p :,i ) max(p :,i ) -min(p :,i ) . ( 7
)
Then, we incorporate the normalized positions of local features into the Improved Fisher Vectors model, so that videos are represented using both local descriptors and their spatio-temporal positions.

Let Y = {y t = [p t , x t ], t = 1 . . . T } be a set of local features, where x t ∈ R D is a local feature descriptor and pt ∈ R E is its corresponding normalized position, typically E = 3, calculated as above. Let λ = { wi , μi , Σi , i = 1 . . . K} be parameters of a GMM u λ(y) = K i=1 wi u i (y) fitting the distribution of local features, where wi ∈ R, μi ∈ R D+E and Σi ∈ R (D+E)×(D+E) are respectively the mixture weight, mean vector and covariance matrix of the i-th Gaussian. As before, we assume that the covariance matrices are diagonal and we denote by σ2 i the variance vector, i.e. Σi = diag(

σ 2 i ), σ2 i ∈ R D+E . We calculate G Y μ,i
(Eq. 2) and G Y σ,i (Eq. 3) for all K Gaussian components, and concatenate all the gradient vectors into a vector G Y λ . Finally, the new Improved Fisher Vectors representation is the gradient vector G Y λ normalized by the power normalization and then the L2 norm:

Φ Y λ = [ G Y μ,1 , G Y σ,1 , . . . , G Y μ,K , G Y σ,K ] √ +l2 . (8)

Fast IFV-based Sliding Window

Our goal is to determine if a violence occurs in a video and when it happens; therefore, we search for a range of frames which contains violence. We base our approach on the temporal sliding window [START_REF] Klaser | Human Focused Action Localization in Video[END_REF] which evaluates video sub-sequences at varying locations and scales.

Let v l be a video length (in frames), s > 0 be the window step size (in frames), and w = {is} i=1...m be temporal window sizes (scales) for the sliding window algorithm. Moreover, let v = ns be an approximated video length (where: ns ≥ v l > (n -1)s and n ≥ m ≥ 1). Visualization of a sample video and sample sliding windows is presented in Fig. 1. Note the IFV are calculated for features from the same temporal segments multiple times, i.e. m(n -m + 1) times for m segments (e.g. Fig. 1: 20 times for 8 segments). Therefore, to speed up the detection framework, we re-formulate the IFV and use the summed area table data structure, so that the IFV are calculated for features from the temporal segments only ones.

Let X = {x t , t = 1 . . . T } be a set of T local features extracted from a video. Let X = {X j , j = 1 . . . N } be a partition of a set X into N subsets ∀ N j =k, j,k=1 X j ∩ X k = ∅ and φ(j, k) → t is the mapping function such that x j,k = x t . We re-write Eq. ( 2):

X j = {x j,k } |Xj | k=1 such that: |X j | is the cardinality of the set X j , X = N j=1 X j , time - • • • s 1 s 2 s 3 s 4 s 5 s 6 s 7 s 8 • • • 6 6 6 6
G X µ,i = 1 T √ w i T t=1 γ t (i) x t -µ i σ i = 1 T √ w i N j=1 |Xj | k=1 γ φ(j,k) (i) x φ(j,k) -µ i σ i = 1 T N j=1 G Xj µ,i |X j | = 1 T N j=1 H Xj µ,i , H Xj µ,i = G Xj µ,i |X j | = 1 √ w i |Xj | k=1 γ φ(j,k) (i) x φ(j,k) -µ i σ i . (9)
Similarly, we re-write Eq. ( 3):

G X σ,i = 1 T √ 2w i T t=1 γ t (i) (x t -µ i ) 2 σ 2 i -1 = 1 T √ 2w i N j=1 |Xj | k=1 γ φ(j,k) (i) (x φ(j,k) -µ i ) 2 σ 2 i -1 = 1 T N j=1 G Xj σ,i |X j | = 1 T N j=1 H Xj σ,i , H Xj σ,i = G Xj σ,i |X j | = 1 √ 2w i |Xj | k=1 γ φ(j,k) (i) (x φ(j,k) -µ i ) 2 σ 2 i -1 . (10)
Then, let's define the gradient vector H Xj λ as a concatenation of all the K gradient vectors H Xj µ,i and all the K gradi-ent vectors H Xj σ,i , i = 1 . . . K:

H Xj λ = [ H Xj µ,1 , H Xj σ,1 , . . . , H Xj µ,K , H Xj σ,K ] . (11)
The Improved Fisher Vectors representation Φ X λ of local features X = N j=M X j , where 1 < M ≤ N , can be calculated using:

G N j=M Xj λ = H N j=1 Xj λ -H M -1 j=1 Xj λ N j=1 |X j | - M -1 j=1 |X j | , ( 12
)
and applying the power normalization and then the L2 norm to the obtained gradient vector. The obtained representation is exactly the same as if we use Eq. ( 2)-( 5). However, in contrast to the original IFV, the above equations can be directly used with data structures such as summed area table (Integral Images) and KDD-trees.

For the task of violence localization, we use the above formulation of the IFV (Eq. ( 9)-( 12)), and directly apply the summed area table (Integral Images [START_REF] Tuzel | Region Covariance: A Fast Descriptor for Detection And Classification[END_REF]). The 2 main advantages of this solution are: (1) it allows to speed up the calculations, as every feature is assigned to each Gaussian exactly once; e.g. we detected 25k features in a 84 frames long video. With m = 4 and s = 5, every feature was assigned to each Gaussian 4 -10 times; this is like 224k features were assigned to each Gaussian. In our algorithm, each feature is assigned to each Gaussian exactly once. This means nearly 9 times less calculations. (2) it allows to reduce the memory usage, especially when a video contains a lot of motion and dense features are extracted [START_REF] Wang | Action Recognition with Improved Trajectories[END_REF]; e.g. we extracted ∼130k features in a 35 seconds long video (∼3.7k features per second on average). With Improved Dense Trajectories [START_REF] Wang | Action Recognition with Improved Trajectories[END_REF] (each trajectory is represented using 426 floats), this means ∼1.6M floats to store per second (segment), which is 29 times more than the IFV representation with 128 Gaussians calculated for this segment.

Experimental Setup: Approach Overview

Firstly, we extract local spatio-temporal features in videos, and we use the Improved Dense Trajectories (IDT) [START_REF] Wang | Action Recognition with Improved Trajectories[END_REF] for that; we apply a dense sampling and track the extracted interest points using a dense optical flow field. Then, we extract local spatio-temporal video volumes around the detected trajectories, and we represent each trajectory using: Histogram of Oriented Gradients (HOG) capturing appearance information, and Trajectory Shape (TS), Histogram of Optical Flow (HOF) and Motion Boundary Histogram (with MBH-x and MBH-y components) descriptors capturing motion information. The extracted IDT features provide a good coverage of a video and ensure extraction of meaningful information. As the results, they have shown to achieve excellent results for various recognition tasks in videos and they have been widely used in literature [START_REF] Bilinski | Video Covariance Matrix Logarithm for Human Action Recognition in Videos[END_REF][START_REF] Wang | Action Recognition with Improved Trajectories[END_REF].

To represent a video, we calculate a separate video representation for each descriptor independently (i.e. HOG, etc.) using the IFV / proposed Spatio-Temporal IFV (Sec. 2.2), and we concatenate the obtained representations using late fusion (i.e. per video: we concatenate the IFVbased video representation from HOG with video representation from HOF, etc.).

For violence recognition, we use linear Support Vector Machines (SVMs) [START_REF] Chang | LIBSVM: A Library for Support Vector Machines[END_REF] classifer, which has shown to achieve excellent results with high-dimensional data such as Fisher Vectors; as typically if the number of features is large, there is no need to map data to a higher dimensional space [START_REF] Hsu | A Practical Guide to Support Vector Classification[END_REF]. Moreover, linear SVMs have shown to be efficient both in training and prediction steps.

For violence detection, we use the Fast Sliding Windowbased framework, explained in Sec. 2.3.

Experiments

Datasets

We use 4 benchmark datasets for evaluation and we follow the recommended evaluation protocols provided by the authors of the datasets. We use Violent-Flows dataset [START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF], Hockey Fight dataset [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] and Movies dataset [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] for violence recognition task. We use Violence-Flows 21 dataset [START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF] for violence detection task. Sample video frames from the datasets are presented in Fig. 2.

The Violent-Flows (Crowd Violence \ Non-violence) dataset [START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF] contains 246 videos with real-world footage of crowd violence. Videos are collected from YouTube and contain a variety of scenes, e.g. streets, football stadiums, volleyball and ice hockey arenas, and schools. The dataset is divided into 5 folds and we follow the recommended 5folds cross-validation to report the performance.

The Hockey Fight dataset [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] contains 1000 real-world videos: 500 violent scenes (between two and more participants) and 500 non-violent scenes. Videos are divided into 5 folds, where each fold contains 50% violent and 50% nonviolent videos, and we follow the recommended 5-folds cross-validation to report the performance.

The Movies dataset [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] contains 200 video clips: 100 videos with a person-on-person fight (collected from action movies) and 100 videos with non-fight scenarios (collected from various action recognition datasets). This dataset contains a wider variety of scenes than the Hockey Fight dataset, and scenes are captured at different resolutions [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF]. Videos are divided into 5 folds and we follow the recommended 5-folds cross-validation to report the performance. Although this dataset does not contain surveillance videos, it has been widely used in the past for violence recognition task.

The main differences between above datasets are: various scenarios and scenes, violence/fight and nonviolence/non-fight classes variations, number of training and testing samples, pose and camera view point variations, motion blur, background clutter, occlusions, and illumination conditions.

The Violent-Flows 21 dataset (Crowd Violence \ Nonviolence 21 Database) [START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF] contains 21 videos with realworld video footage of crowd violence. Videos are collected from YouTube, they are of spatial size 320×240 pixels, and they begin with non-violent behavior, which turns to violent mid-way through the video. The training is performed using 227 out of 246 videos from the Violent-Flows dataset; 19 videos are removed as they are included in the detection set. The original annotations are not available. Therefore, as proposed in the original paper [START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF], we manually mark the frame in each video where the transition happens from non-violent to violent behavior 1 .

Implementation Details

We use the GMM with K = 128 and K = 256 to compute the IFV / Spatio-Temporal IFV, and we set the number of Gaussians using 5-folds cross-validation. To increase clustering precision, we initialize the GMM 10 times and we keep the codebook with the lowest error. To limit the complexity, we cluster a subset of 100, 000 randomly selected training features. To report recognition results, we use the Mean Class Accuracy (MCA) metric. For violence detection, we use six temporal windows of length {5i} 6 i=1 frames and the window stride equal to 1 frame. To report 1 Differences can exist between our and [START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF] annotations. detection results, we use the Receiver Operating Characteristic (ROC) curve and the Area Under Curve (AUC) metrics.

Results: Violence Recognition

For violence recognition, we evaluate the standard IFV approach (baseline approach) and our IFV with spatiotemporal information (STIFV, Sec. 2.2). Moreover, we evaluate the IFV with 11 various spatio-temporal grids (1x1x2, 1x2x1, 2x1x1, 1x1x3, 1x3x1, 3x1x1, 2x2x2, 2x2x3, 2x2x1, 2x1x2, and 1x2x2). The evaluations are performed on 3 datasets: Violent-Flows, Hockey Fight and Movies datasets. The results are presented in Table 1. In all cases, our STIFV approach outperforms the IFV method, and achieves better or similar performance as compared to the IFV with spatio-temporal grid. Note that finding an appropriate size of the spatio-temporal grid is time consuming (there are 3 additional parameters to learn). Moreover, a spatio-temporal grid-based representation requires significantly more amount of memory (up to 12 times in our experiments, see Table 1).

Then, we compare our approach with the state-of-theart. The comparison on the Violent-Flows, Hockey Fight, and Movies datasets is presented in Table 2. Note that our approach significantly outperforms remaining techniques, achieving even up to 11% better results (on the Violent-Flows dataset).

In summary, for violence recognition, the proposed improvement (IFV with spatio-temporal information) boosts the state-of-the-art IFV, and achieves better or similar ac-

Violent-Flows Dataset Hockey Fight Dataset

Movies Dataset Approach Acc. (%) HNF [START_REF] Laptev | Learning realistic human actions from movies[END_REF] 56.5 HOG [START_REF] Laptev | Learning realistic human actions from movies[END_REF] 57.4 HOF [START_REF] Laptev | Learning realistic human actions from movies[END_REF] 58.3 LTP [START_REF] Yeffet | Local Trinary Patterns for human action recognition[END_REF] 71.5 Jerk [START_REF] Datta | Person-on-Person Violence Detection in Video Data[END_REF] 74.2 Interaction Force [START_REF] Mehran | Abnormal Crowd Behavior Detection using Social Force Model[END_REF] 74.5 ViF [START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF] 81.3 HOT [START_REF] Mousavi | Analyzing Tracklets for the Detection of Abnormal Crowd Behavior[END_REF] 82.3 F L |F Cv [START_REF] Mohammadi | Violence detection in crowded scenes using substantial derivative[END_REF] 85.4 Our Approach 96.4

Approach Acc. (%) LTP [START_REF] Yeffet | Local Trinary Patterns for human action recognition[END_REF] 71.9 ViF [START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF] 82.9 STIP-HOF + HIK [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] 88.6 Extreme Accelerations [START_REF] Daniz | Fast Violence Detection in Video[END_REF] 90.1 MoSIFT + HIK [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] 90.9 BoW-MoSIFT [START_REF] Daniz | Fast Violence Detection in Video[END_REF] 91.2 STIP-HOG + HIK [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] 91.7 Our Approach 93.7

Approach Acc. (%) STIP-HOG + HIK [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] 49 STIP-HOF + HIK [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] 59 BoW-MoSIFT [START_REF] Daniz | Fast Violence Detection in Video[END_REF] 86.5 MoSIFT + HIK [START_REF] Nievas | Violence Detection in Video Using Computer Vision Techniques[END_REF] 89.5 ViF [START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF] 91.3 Jerk [START_REF] Datta | Person-on-Person Violence Detection in Video Data[END_REF] 95.0 Interaction Force [START_REF] Mehran | Abnormal Crowd Behavior Detection using Social Force Model[END_REF] 95.5 F L |F Cv [START_REF] Mohammadi | Violence detection in crowded scenes using substantial derivative[END_REF] 96.9 Extreme Accelerations [START_REF] Daniz | Fast Violence Detection in Video[END_REF] 98.9 Our Approach 99.5 Approach LTP HOG HOF HNF VIF Ours AUC 79.9 61.8 57.6 59.9 85.0 87.0 curacy (keeping the representation more compact) as compared to the IFV with spatio-temporal grids. Moreover, our approach significantly outperforms the existing techniques on all three violence recognition datasets.

Results: Violence Detection

We evaluate our Fast Sliding Window-based approach on the Violence-Flows 21 dataset.

Firstly, we evaluate the accuracy of the sliding window / Fast Sliding Window approach (both techniques achieve the same results). The results and comparison with the state-ofthe-art are presented in Figure 3 (using the ROC curves) and in Table 3 (using the AUC metric).

Then, we evaluate the speed of the Improved Dense Trajectories (IDT), and we compare the speed of the standard sliding window approach with the speed of our Fast Sliding Window technique (Sec. 2.3). The results are presented in Table 4. We observe that the proposed Fast Sliding Window technique is more than 10 times faster than the standard sliding window approach.

Conclusions

We have proposed an extension of the Improved Fisher Vectors (IFV) for violence recognition in videos, which allows to represent a video using both local features and their spatio-temporal positions. The proposed extension has shown to boost the IFV achieving better or similar accuracy (and keeping the representation more compact) as compared to the IFV with spatio-temporal grid. Moreover, our approach has shown to significantly outperform the existing techniques on three violence recognition datasets. Then, we have studied the popular sliding window approach for violence detection. We have re-formulated the IFV and have used the summed area table data structure to significantly speed up the violence detection framework. The evaluations have been performed on 4 state-of-the-art datasets.

Figure 1 .

 1 Figure 1. Temporal sliding window: a sample video is divided into n ≥ 8 segments. We use m = 4 window scales. Note that the IFV are calculated for features from the same segments multiple times (20 times for 8 segments).

Figure 2 .

 2 Figure 2. Sample video frames from the Violent-Flows (first row), Hockey Fight (second row), Movies (third row), and Violent-Flows 21 (fourth row) datasets.

Figure 3 .

 3 Figure 3. ROC curves: our approach (on the left) vs. the state-ofthe-art (on the right) on the Violent-Flows 21 dataset.

Table 1 .

 1 Evaluation results: the baseline (IFV with 1x1x1) approach, our IFV with spatio-temporal information (STIFV), and the IFV with various spatio-temporal grids on the Violent-Flows, Hockey Fight, and Movies datasets. Second column presents the size of the video representation relatively to the size of the video representation of the baseline approach.

	Approach	Size Violent-F. Hockey F. Movies
	Baseline	1	93.5	93.2	97
	Ours: STIFV ∼1	96.4	93.4	99
	IFV 1x1x2	2	94.0	93.3	98.0
	IFV 1x2x1	2	94.3	93.6	97.5
	IFV 2x1x1	2	94.3	93.2	97.5
	IFV 1x1x3	3	93.5	93.1	98.5
	IFV 1x3x1	3	94.3	93.2	97.0
	IFV 3x1x1	3	93.5	93.2	97.5
	IFV 2x2x2	8	93.5	93.4	97.0
	IFV 2x2x3	12	93.1	93.4	97.0
	IFV 2x2x1	4	93.9	93.8	97.5
	IFV 2x1x2	4	93.5	92.9	98.0
	IFV 1x2x2	4	93.9	93.5	97.5

Table 2 .

 2 Comparison with the state-of-the-art on the Violent-Flows (left table), Hockey Fight (middle), and Movies (right) datasets.

Table 3 .

 3 AUC metric on the Violent-Flows 21 dataset[START_REF] Hassner | Violent Flows: Real-Time Detection of Violent Crowd Behavior[END_REF].

	Process	Processing Time (fps)
	Feature Extraction (IDT)	5.7
	Sliding Window	9.28
	Ours: Fast Sliding Window	99.21

Table 4 .

 4 Average processing time on the Violent-Flows 21 dataset using a single Intel(R) Xeon(R) CPU E5-1630 v3 @ 3.70GHz.

Acknowledgements.

The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme FP7/2007-2013/ under REA grant agreement n o [324359]. However, the views and opinions expressed herein do not necessarily reflect those of the financing institutions.


Jana Trojanová
email: jana.trojanova@honeywell.com

Karel Křehnač

François Brémond

Data-Driven Motion Pattern Segmentation in a Crowded Environments

Motion is a strong clue for unsupervised grouping of individuals in a crowded environment. We show that collective motion in the crowd can be discovered by temporal analysis of points trajectories. First k-NN graph is constructed to represent the topological structure of point trajectories detected in crowd. Then the data-driven graph segmentation helps to reveal the interaction of individuals even when mixed motion is presented in data. The method was evaluated against the latest state-of-the-art methods and achieved better performance by more than 20 percent.

Introduction

Understanding crowd dynamics in complex environments remains an open problem in computer vision due to a large number of individuals exhibiting diverse movement. The crowd dynamics evolve depending on each individual's will as well as that of his neighbors. The variety of interactions among individuals is what makes the task of crowd understanding a difficult problem. Some individuals can exhibit an aggregated motion while others can move independently. Fig. 1 shows an example of motion pattern segmentation interpreting these interactions. The term motion pattern here represents a spatial region with coherent flow in comparison to its neighboring regions.

Prior research in motion pattern segmentation can mostly be classified into two groups: flow field model-based segmentation and similarity model-based clustering. The first one simulates a moving crowd as a time dependent flow field. The flow field consists of regions with quantitatively different dynamics and motion patterns emerge from the spatio-temporal interactions of individuals. They build on optical flow alike features and use methods such as edge-based segmentation, graph-based segmentation or watershed segmentation. These methods can well describe the structured crowd motion and are the most studied in the motion pattern segmentation. However, they are temporally inconsistent over a longer video shot and work only for high crowd density otherwise the video scene would be over-segmented. A nice overview of such methods can be found in [START_REF] Li | Circuits and Systems for Video Technology[END_REF].

The second group of methods uses the principle of clustering. Once lowlevel motion features are detected they are grouped based on some similarity measurements or fitted with a probability model. The boom with similaritybased clustering is linked with the success of local motion features such as short Frame 54 Brox Fig. 1. Segmented motion patterns (or groups segregation) as the crowd evolves in time. The color of point represents the assignment to a group. While groupings are temporally consistent over a set of frames for Brox [START_REF] Keuper | Motion trajectory segmentation via minimum cost multicuts[END_REF] and Our method. Zhou [START_REF] Zhou | Measuring crowd collectiveness[END_REF] and Shao [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF] fail to maintain consistent groupings between frames.

point trajectories which can be obtained more easily than the whole trajectory. These points trajectories are more discriminative than local optical flows. The similarity clustering methods can handle structured and unstructured crowds.

Representatives of such methods are [START_REF] Wang | Finding coherent motions and semantic regions in crowd scenes: A diffusion and clustering approach[END_REF][START_REF] Wu | Coherent motion detection with collective density clustering[END_REF]. Recently, probability models showed high potential in discovering semantic regions. Even though the methods can well capture overlapping behaviors and spatial dependencies among them, they require the whole video in advance to learn the probability model [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF]. As will be shown in the experiment section the temporal consistency over a longer video shot is not always maintained.

Our framework builds on principles of both groups. No training is required and motion patterns are revealed by temporal analysis of point trajectories detected on a set of 15 frames. First of all an oriented graph is constructed based on k-nearest neighbor of points trajectories. Each node of the graph represents an averaged trajectory. The objective is to keep only the compact neighbor nodes with high collective motion. To do so the graph edges are weighted by correlation among two connected nodes. The graph is segmented by a single threshold to keep nodes with high collective motion. This results in small compact neighbor groups. Clustering is applied to merge compact neighbor groups with similar motion. The propagation of similar motion through neighbors allow us to discover coherent motion in the whole crowded environment. Fig. 1 illustrates the capability of our method on crowd data ranging from low to high density.

The automatic motion pattern segmentation in a crowded environment has been an active topic in computer vision for more than one decade. Comparison of the methods is typically done on crowd videos downloaded from the web. The evaluation is done visually on selected videos. Authors often select a set of examples where they have better results than the competing method. Some works annotates the boundary of the crowd and its main direction, but the evaluation only compares the correct direction of the motion patterns. To our knowledge only one public crowd database provides annotation and evaluation respecting motion patterns. The CUHK database [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF] has annotation for 300 videos. In each video, a set of 30 frames was selected and detected tracklets were grouped based on the collective motion of individuals. The representation is similar to motion pattern definition, but instead of region only detected tracklets are used to define group segregation.

Moreover, we have found inconsistency and many mistakes in data annotation of the CUHK dataset; see section 3 for more details. The re-annotation we made for the subset of the CUHK database draws the boundary of the motion patterns for a set of frames and captures motion overlaps among motion patterns. The proposed annotation helps to reveal the groupings consistency across a given set of frames. We have benchmarked our results against two state-of-the-art methods and show that in the situation where groups are well segregated (lowmotion overlap across set of frames) all state-of-the-art methods provide reliable output. The performance deteriorates with increasing level of mixed motion in the input data.

Related Work

Segmentation of crowd scenes based on motion has attracted a significant amount of research works. Obtained motion patterns can be used in a wide range of applications like tracking in crowd [START_REF] Rodriguez | Data-driven crowd analysis in videos[END_REF], sink and source seeking [START_REF] Jodoin | Meta-tracking for video scene understanding[END_REF], or anomaly detection [START_REF] Wang | Finding coherent motions and semantic regions in crowd scenes: A diffusion and clustering approach[END_REF]. A recent survey on motion pattern segmentation methods can be found in [START_REF] Li | Circuits and Systems for Video Technology[END_REF]. Here we concentrate on methods missing from the survey.

The feature extraction is a crucial step and each subsequent task benefits from its clear representation. A high density of people in the crowd performing various irregular motion leads to frequent occlusions. Traditional object detection and tracking algorithms, which are also computationally expensive for a large number of objects, often fail in the case of severe occlusions [START_REF] Li | Circuits and Systems for Video Technology[END_REF]. The trend is to use pixelbased features, because in high density crowds the local motion features such as point trajectories can be obtained more easily. The generalized KLT tracker [START_REF] Wu | Coherent motion detection with collective density clustering[END_REF][START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF] or Lagrangian framework [START_REF] Wang | Finding coherent motions and semantic regions in crowd scenes: A diffusion and clustering approach[END_REF] are quite popular. The provided trajectories capture the actual motion of the crowd and are useful for wide fields of view with low resolution.

Promising results have been shown in [START_REF] Wang | Finding coherent motions and semantic regions in crowd scenes: A diffusion and clustering approach[END_REF] where coherent motion is detected based on an analysis of Lagrangian particles. On top of that two-step clustering is applied to construct stable semantic regions from detected time-varying coherent motion. They made a comparison to six state-of-the-art methods on a selected subset of videos. Neither data with annotation or code is provided to the public. Thus we are unable to compare our work to such a promising method.

An interesting characteristic called the crowd collectiveness descriptor has been proposed in [START_REF] Zhou | Measuring crowd collectiveness[END_REF]. The collectiveness indicates the degree of individual acting as union in collective motion. The descriptor measures the collectiveness in single frame. The grouping consistency between frames is not maintained at all as shown in fig. 1. Nevertheless the method has a great potential to be extended into temporal domain as shown in [START_REF] Wu | Coherent motion detection with collective density clustering[END_REF] and [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF].

Collective density clustering was proposed in [START_REF] Wu | Coherent motion detection with collective density clustering[END_REF] to recognize local and global coherent motion for varying crowd density. The method was benchmarked against [START_REF] Zhou | Measuring crowd collectiveness[END_REF] on the Collective Motion Database. The goal was to compare the correct level of collective motion (low, medium, and high). There are only visual examples showing the motion pattern segmentation against state-of-the-art method and one comparison on correct direction detection. The code is not provided therefor we can not compare our work to this method.

In [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF] the crowd collectiveness descriptor is used to learn the collective transition priors from a given set of frames. The crowd is analyzed at the grouplevel where a group is considered as a set of members with a common goal and collective behaviors. The approach provides consistent group segregation in a crowded environment with low motion overlap. Yet the method fails to maintain the consistent groups segregation in complex crowded environment as illustrated in fig. 1. The groups segregation is equivalent to the motion pattern definition we have. The authors provide a database with annotation and source code. The comparison can be found in our experiments.

We conclude our review with a recent method for object segmentation driven by motion [START_REF] Keuper | Motion trajectory segmentation via minimum cost multicuts[END_REF]. The graph among each point of a trajectory is formed and minimum cost multicuts function is applied to precisely segment moving object from the scene. The method has incorporated motion, color and spatial distance into the graph to represent the relation between trajectories. The grouping consistency is maintained, but color distance can assign similar individuals with different motion to same group. On top of that it requires extensive training with precisely annotated training data. As the source code is provided we compare our work to this method.

The main contributions of our approach can be concluded as follows:

-We show how to simply extend the crowd collectives descriptor designed for a single frame to the temporal domain by averaging the point trajectories across fixed set of frames. The proposed framework results in temporally consistent groupings of individuals capable of segmenting arbitrary shapes of groups for structured and unstructured crowds with various crowd densities. -Temporal analysis of point trajectories across a set of frames introduces the problem of overlapping motion patterns. Our framework does not require any training, only one parameter is hardwired. The number of neighbours for k-NN graph construction is set to represent up to four overlapping motion patterns in a particular image area. -The threshold for graph segmentation is not fixed but it is data-driven and thus better represents the actual motion presented in the crowd. The results on subset of the CUHK dataset show higher accuracy for overlapping motion patterns against the state-of-the-art method.

Motion pattern segmentation framework

The idea is that collective motion in the crowd can be discovered by temporal analysis of points trajectories. The analysis of long-term point trajectories has been very popular recently. It played an important role in works related to motion segmentation [START_REF] Keuper | Motion trajectory segmentation via minimum cost multicuts[END_REF][START_REF] Wu | Coherent motion detection with collective density clustering[END_REF][START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF]. These trajectories are called tracklets, and provide pixel movement in a given set of frames. Nevertheless other optical-flow-based trajectories like large displacement optical flow [START_REF] Weinzaepfel | Deepflow: Large displacement optical flow with deep matching[END_REF] can be used as input to our framework. Here we stick to dense trajectories presented in [START_REF] Wang | Action recognition with improved trajectories[END_REF] since they can filter out movement caused by camera motion. The basic setting is used providing reliable points tracklets for 15 consecutive frames. We use the similarity graph from the spectral clustering [START_REF] Von Luxburg | A tutorial on spectral clustering[END_REF] to represent the topological structure of tracklets detected in crowded video scene. We show how to take advantage of the collectiveness descriptor [START_REF] Zhou | Measuring crowd collectiveness[END_REF] and design criteria for the automatic threshold selection used for the graph segmentation. Fig. 2 shows a basic simplified flowchart. The input shows trajectories of four points groups with different directions. Each group of points is starting at different sides of the image and the overlap of their trajectories occurs in the middle of the image. The tracklet of each point is averaged for a given period of time (in this case whole tracklet) and the graph is constructed based on the k-nearest neighbor (k-NN) of averaged tracklets. During graph segmentation with the automated threshold selection, edges with dissimilar motion are cut-off. Only edges with high collective motion remain in the graph. Having obtained a graph connecting nodes with high collective motion, clustering is applied to find coherent motion patterns. The motion patterns can be used in various applications. In this particular work, we concentrate on the overlapping motion pattern segmentation and its evaluation on the CUHK dataset [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF]. The individual components of the framework are described next.

Graph construction

Interactions of neighbours play an important role in crowded environments. To capture the topological structure of these interactions we construct a similarity graph such that every averaged tracklet is represented by a node v v = (x, ȳ, ∂x, ∂y)

where the first two values are coordinates of the averaged tracklet and the last two represent the average velocity of the tracklet. Every node v is connected via a edge to each of its k-nearest neighbours nodes. Adjacency Matrix A is used to represent the oriented k-NN graph. Matrix rows and columns are labeled with graph nodes v ∈ V . Matrix entries at position (v i ,v j ) are 1 or 0, depending on whether v i and v j are connected or not. The matrix A has zero entries on the diagonal, since no tracklet connects to itself.

First we create an adjacency matrix based on k-nearest neighbours of each node. Each line of matrix A (each node with its neighbours) forms a small group of tracklets. In a real scenario noise is present in the data and single distant nodes can connect to the graph. Thus a distance threshold is applied to remove distant nodes from the matrix A with entry 1 as follows

A Dist (v i , v j ) = 1, if A(v i , v j ) = 1 ∧ d(v i , v j ) < µ D + σ D 0, otherwise (2)
µ d = 1 N A(vi,vj )=1) d(v i , v j ) (3)
σ d = A(vi,vj )=1) 1 N (d(v i , v j ) -µ d ) 2 (4)
where d(v i , v j ) is the Euclidean distance between two nodes, µ D and σ D is the average distance and the distance standard deviation between all nodes in matrix A, N is the sum of entries when matrix A(v i , v j ) = 1.

Fig. 3 illustrates the effect of k-NN number selection on graph clustering. In the case when a small number of neighbours is selected the collective motion can not be revealed (first two columns in fig. 3). Thus we seek the minimum number of neighbors to get precise motion patterns. This number depends on the motion overlap present in the data. For no overlapping movement, K = 3 is enough, for partial overlap K = 5 is required. For complete overlap K = 20 is required. The lower value of k would result in scattered areas, while a higher number of neighbours would result in the same clustering output. The optimal number of k to reveal up to four mixed motion at a particular segment of the image in 15 consecutive frames is set to k = 20 based on empirical evidence. The larger number of neighbours also helps to overcome the noise produced by dense trajectories at a particular area of the image.

In contrast in [START_REF] Zhou | Measuring crowd collectiveness[END_REF] the path-based similarity is used to characterize the behavior consistency among individuals. The k-walk through the graph is used to obtain individual collectiveness. The weight between edges for similar nodes increases within the distance of k neighbours and decreases for dissimilar nodes. The parameter k defines the length of path over which the weight of the edge will be computed. Application of the k-walk through the graph helps to segment the graph, on the other hand increasing the length of path results in oversegmentation of the graph. In our representation the graph is used to capture the topological structure among tracklets. The weight of the graph edge and its segmentation is defined in the next section.

Graph Segmentation

The non-zero entries of adjacency matrix A Dist are weighted based on velocity correlation among a given pair of nodes and forms weighted adjacency matrix

W (v i , v j ) = corr(v i , v j ), if A Dist (v i , v j ) = 1 0, otherwise (5)
The matrix W characterizes the behavior consistency among neighbouring individuals in the crowd. The maximum value of matrix W is 1 and it means that nodes have the same direction of velocity vectors. If two connected tracklets move in the same direction and have highly correlated motion we want to preserve the edge, otherwise the edge should be removed from the graph. By applying the threshold T on the matrix W , we ensure that only highly correlated neighbors remain in the graph. The selection of threshold from interval T ∈ (0, 1) is driven by data. We make use of the collectiveness descriptor from [START_REF] Zhou | Measuring crowd collectiveness[END_REF] and define individual collectiveness for each node v i and its neighbours as

φ vi (T ) = 1 N i W >T w(v i , v j ) (6)
where N i is number of edges connected to node v i after applying threshold T and φ vi thus represents the mean correlation value between node v i and its neighbours v j higher than threshold T . Each node and his neighbours form a small group. While in Zhou [START_REF] Zhou | Measuring crowd collectiveness[END_REF] the collectiveness was computed for one fixed threshold, here we change the threshold to evaluate the collectiveness of each group. The φ vi (T ) measures the individual collectiveness of the group. Now we can define collectiveness criteria for optimal threshold selection as follows

T * = argmax T ∈<0,1> ( N T N G • 1 N G W >T φ vi ) (7)
the criteria measures normalized average collectiveness for all individual groups, N G is the number of groups, and N T is the number of groups with individual collectiveness bigger than the threshold. Fig. 4 shows the value of the criteria for threshold values in interval T ∈ (0, 1) on a subset of the CUHK dataset. For each video segment we have one criteria curve. The value of the criteria for the minimum threshold T = 0 serves as a measure of how much structured motion is present in the video segment. The criteria value for each threshold tell us how big the collectiveness is across all groups formed in the graph.

In the ideal case (top line in fig. 4) when velocity vectors are highly correlated across the whole sequence, the criteria curve remains the same for a long interval of threshold T . This tell us that graph nodes are well separated no matter which value of T we select and the motion of each group is highly correlated.

The decrease in criteria value is caused by lower correlation between the node and its neighbours which form a group. The threshold value T = 1 means that we don't allow any velocity difference between connected nodes. Lowering the threshold means that we allow some difference, but the question is how to define the exact of the velocity variation that is permitted? We seek the optimal balance between the number of groups and their average collectiveness represented by the maximum value of the criteria defined in equation 7. The threshold for each video sequence is optimized using the golden section search method. After applying the threshold T * on matrix W each node preserves the edges with high correlation and cut-off the rest.

Graph Clustering

Having obtained a segmented graph that forms small compact groups (neighbours around each node) we can proceed with clustering. The existing graph edges maximize average collectiveness across the whole video segment. But the segmented graph tell us only the link between closest nodes. Now we want to cluster the graph nodes to form the motion pattern.

Fig 5 illustrates the clustering on a simple example. The decision whether to merge the neighbour's nodes depends on the correlation between the parent node and its children. The threshold value for graph segmentation defines how big variation is allowed between two nodes. Ideally this value would be set to 1 and only same direction nodes will be connected. In real data the threshold is typically around 0.95 which means 5% variation between two nodes is allowed. We recursively search through the graph and look if parent/children correlation fits the threshold. If all the children meet the threshold the neighbour node is merged in the same cluster as the parent node. If any of the children violate the correlation threshold the recursive search for the neighbour node is stopped. The clustering reflects arbitrary shapes appearing in the crowd while allowing varying size of clusters. The proposed framework is capable of segmenting motion patterns for various levels of density, from highly aggregated motion to low density disconnected areas.

Experiments on the CUHK dataset

The proposed framework is evaluated on a challenging subset of the CUHK video dataset [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF]. We first describe the details about the dataset and drawbacks of the provided annotation. Then we demonstrate the results obtained for our method versus state-of-the-art [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF][START_REF] Keuper | Motion trajectory segmentation via minimum cost multicuts[END_REF].

The CUHK dataset provides annotation for 300 segments for varying length of video segment ranging from 7 up to 67 frames. Annotation of the data was made for tracklets found by the generalized KLT tracker. The tracklets are grouped based on the criterion that members in the same group have a common goal and form collective movement. Tracklets not belonging to any group are annotated as outliers. Fig. 6 show inconsistency and mistakes observed in data annotation. More than 50% of data have inconsistency in terms of merging distant groups versus splitting neighbours to different groups. Moreover serious mistakes like ignoring the opposite direction of individuals or noise tracklets assigned to the nearest group were discovered. Thus we have decided to re-annotate the database.

The full CUHK dataset contains repeating scenes clipped in separate video segments. From the set of 300 annotated video segments there are actually 140 unique scenes, the rest are the same views for different time window. The database consist of scenes like marathon runners, military marching, protesting pedestrians, escalators, cross walk, public transport stations, shopping malls or people walking in the street.

We have further divided the database to simple and complex scenarios. In simple scenarios the groups of individuals can be easily segregated while in com-Fig. 6. Figure illustrates the annotation inconsistency (first two images in top row) and errors (last two images in top row) in the CUHK database [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF] and our re-annotation (bottom row). First image shows merge of the individuals in blue circles who are separated by individual moving in different direction. In contrast let's look at the second image with pedestrians running in a marathon. All pedestrians are running in same direction, there is no obvious reason to separate the groups, thus we keep them as one. The third image shows that the opposite direction was ignored and merged with the main direction. In the fourth image the escalator movement is merged with the main direction (red circles show observed errors).

plex scenarios the individuals are mixed in a given set of frames. Mixed individuals means that at a particular part of the image pedestrians move in more than one direction (e.g. cross-walk). Both scenarios typically have a crowd moving in one or two main directions with some individuals moving independently. Two-thirds of the CUHK data contain simple scenarios, the rest is considered as complex scenarios. Some of the complex scenarios are so challenging that annotation of such videos would be very arguable. Thus we selected 25 out of 40 complex scenarios and 25 out of 100 for simple scenarios.

The selected 50 videos spans a wide range of crowded scenes covering different pedestrian size and various crowd densities. Fig. 6 compares the original annotation to our new one. The ground truth provides boundary information and main direction of the motion pattern. Two annotators cross-validate their outputs. The boundary is drawn to capture spatial region with coherent flow in a given set of frames. The various speeds (e.g. individuals running on escalators) are ignored. The same starting frame as in [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF] was selected for data re-annotation, each re-annotated set last 30 frames. In total 1500 re-annotated frames are used as a benchmark. Our annotation of groups boundaries for a given set of frames helps to reveal the consistency of individuals grouping between frames.

Results on CUHK data

In order to evaluate the framework we compare its performance against recent state-of-the-art methods proposed in [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF] and [START_REF] Keuper | Motion trajectory segmentation via minimum cost multicuts[END_REF]. We run available binaries on the subset of the CUHK data comprising 1500 re-annotated images. The obtained results are treated as a clustering problem. To benchmark the performance of the methods we use the Purity and F-measure.

Table 1. Results on the subset of the CUHK database for simple (left) and complex (right) scenarios. We report results for D: purity, P: average precision, R: average recall, F: F1-measure. Subscript W represents clusters weighted by their size. The first three rows show unweighted clustering, the last three rows show clustering weighted by the size of the cluster The density of point trajectories between our method and state-of-the-art differs, see fig. 7. Therefore the computation of the true positives (TP), false positive (FP) and false negatives (FN) is based on overlap between the ground truth area and the area drawn around clustered point trajectories.

The cluster switching between frames is misleading. Building an application for abnormal activity recognition on top of the method with cluster switching between frames would produce an enormous number of false alarms. By using the area overlap and evaluation across the whole sequence of 30 frames we also penalize the clustering inconsistency when clusters switch between frames.

The state-of-the-art method has various parameters that can be change for boosting the performance. For the method in [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF] there are 8 parameters. As the available code was tuned for the CUHK dataset we have kept the original setting. For the method in [START_REF] Keuper | Motion trajectory segmentation via minimum cost multicuts[END_REF], we use the available binaries and run the code against the crowd data to see how well the parameters tuned for object segmentation work for crowded environments. Additionally there are two independent parameters: number of frames and threshold. We observe that changing the number of frames from 8 to 15 did not significantly affect the results (change of F-measure was around 0.01%). Only the threshold influences the final number of clusters in the video. The best results were obtained for threshold 0.5.

Tab. 1 provides two types of results, unweighted and weighted. For unweighted results the F-measure uses average precision and recall across all the clusters in the given video. For weighted results the precision and recall for each cluster is weighted by the proportional cluster size. For the unweighted F-measure we outperform the state-of-the-art by 30%. Such a big difference in performance is caused by missed irregular clusters. For instance a single individ-ual walking in a different direction than main clusters, see example in fig. 7. For the weighted F-measure the performance of state-of-the-art increases by 25%, since the methods capture the main clusters. Nevertheless we are still 20% ahead in performance, since our method does not suffer from cluster switching between frames. The methods in [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF][START_REF] Keuper | Motion trajectory segmentation via minimum cost multicuts[END_REF] provide good results for main clusters but lack the capability of detecting the irregular motion of individuals. Moreover, distant individuals are clustered together even if they move in the opposite direction and method in [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF] suffers from cluster switching between the frames.

Conclusion

This paper introduced a framework for motion pattern segmentation in crowded environments. The proposed method is fully unsupervised and uses short tracklets detected by dense trajectories. It reveals the collective motion of individuals independent of the crowd density. Our method can detect different scales of groups with arbitrary shapes and distinguish the big groups and irregular motion of individuals that move otherwise. The resulting grouping of individuals is temporally consistent over the set of frames, a property that requires postprocessing in the existing approaches.

We have tested our approach on a subset of the CUHK database. Experimental results show that our approach outperforms existing state-of-the-art method by more than 20 percent. However, we note that the annotation of motion patterns is subjective and differs between people. In future work we will evaluate our framework on practical applications like unusual event recognition and tracking in crowded environments.

We will conclude this paper by summarising the framework shortcomings. The average tracklet is computed across 15 frames. This was chosen based on the dense trajectory output and provides satisfying results for the given set of videos. In future this property should be also data driven as the dynamic of the crowd evolves in time. For rapidly moving objects, it might happen that the point trajectories are short. In these cases, we would increase the number of frames for computation of the averaged tracklet.

From our understanding of the framework the graph clustering part is the most weak and offers a real scope for improvement. Clustering of the graph should be done from a bigger perspective than just considering the parent and children of the neighbour node. We plan to apply a multi-resolution approach in order to to reduce the over-segmentation of data. Results for a simple scenario with easily separable groups and a complex scenario with mixed groups. The first column shows the ground truth, the next three columns show the output of our method, method A [START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF] and method B [START_REF] Keuper | Motion trajectory segmentation via minimum cost multicuts[END_REF]. The D,F,DW , and FW are defined in tab. 1. The first row shows a scene with two main opposite directions and several individuals highlighted by pink, red, yellow and cyan colors. Our method is capable of recognizing all motion patterns, method A can only recognize two main directions and method B incorrectly assigns two opposite direction as one and creates a separate cluster for cars with a different color from pedestrians. The second row shows a scene where a military unit is marching. All methods correctly cluster the scene. The third row shows a scene with escalators. Method A has inconsistent grouping. Pedestrians in the main direction highlighted in blue are assigned to the pink and yellow clusters for some of the frames. Method B merges distant pedestrians to one group highlighted in pink and over-segments the main direction into three clusters highlighted in blue, yellow and cyan. The last row shows a challenging cross walk scene where people mix together. Our method and method A correctly recognize the clusters. Method B over-segments the pedestrians moving down into two clusters and some distant point trajectories in the bottom are merged with the blue cluster although they move in opposite directions.

Fig. 2 .

 2 Fig. 2. The framework simplified flowchart. The graph is constructed so that each node (averaged tracklet) is connected by edges to k-NN nodes. During the graph segmentation the edges with low collectiveness are cut-off (red dotted lines). Finally, clustering is applied and connected nodes with similar motion are merged. Best viewed in color.

Fig. 3 .

 3 Fig. 3. Visual examples of graph construction for various number of neighbors. First example shows the graph construction for various numbers of k-NN (first column K=1,second K=3, third K=5). The second example shows the constructed graph for high motion overlap. For mixed up motion the minimum number of neighbours is 20.

Fig. 4 .

 4 Fig. 4. The values of collectiveness criteria defined in equation 7 can be seen on the right side. On the left side examples for the highest and lowest criteria curve are shown. The top row shows a visual example for curve marked with a when the criteria value is close to 1 for the threshold interval (0,0.98). It is almost an ideal case where the velocity vectors have a similar direction, their correlation variation is not bigger than 2% . The bottom row shows example for the curve marked with b when the criteria has the lowest value. It shows the hardest example of the CUHK subset. The detail shows that velocity vectors for both directions are mixed. The last column of the figure shows ground truth annotation for selected examples. It can be seen that the criteria value captures the level of motion overlap in input data.

Fig. 5 .

 5 Fig. 5. Visual example of graph clustering through recursive search. Here we start from node 5 and concentrate on neighbour nodes 7 and 11. If the correlation between all of the children nodes and the parent node fits the threshold T the neighbour node 11 is assigned to the same cluster as node 5. Otherwise the recursive search is stopped. Node 7 is eventually assigned to the same cluster through node 11.

5 Acknowledgement

 5 This work was partially supported by the People Programme (Marie Curie Actions) of the European Unions Seventh Framework Programme FP7/2007-2013/ under REA grant agreement n[324359].

Fig. 7 .

 7 Fig.7. Results for a simple scenario with easily separable groups and a complex scenario with mixed groups. The first column shows the ground truth, the next three columns show the output of our method, method A[START_REF] Shao | Learning scene-independent group descriptors for crowd understanding[END_REF] and method B[START_REF] Keuper | Motion trajectory segmentation via minimum cost multicuts[END_REF]. The D,F,DW , and FW are defined in tab. 1. The first row shows a scene with two main opposite directions and several individuals highlighted by pink, red, yellow and cyan colors. Our method is capable of recognizing all motion patterns, method A can only recognize two main directions and method B incorrectly assigns two opposite direction as one and creates a separate cluster for cars with a different color from pedestrians. The second row shows a scene where a military unit is marching. All methods correctly cluster the scene. The third row shows a scene with escalators. Method A has inconsistent grouping. Pedestrians in the main direction highlighted in blue are assigned to the pink and yellow clusters for some of the frames. Method B merges distant pedestrians to one group highlighted in pink and over-segments the main direction into three clusters highlighted in blue, yellow and cyan. The last row shows a challenging cross walk scene where people mix together. Our method and method A correctly recognize the clusters. Method B over-segments the pedestrians moving down into two clusters and some distant point trajectories in the bottom are merged with the blue cluster although they move in opposite directions.