Sparse Subspace Clustering on video volume

Introduction

Sparse Subspace Clustering (SSC) can be used for detection of anomalies based on motion. The trajectory of feature points in a video can be assumed to lie in different affine subspaces. Points on objects with similar motion will tend to cluster in the same subspace. In video sequences, the points can lie in 3 distinct subspaces: 1) for the background 2) for the normal motioned objects (in our case pedestrians) 3) for the anomalies. A general overview of SSC algorithm is discussed.

Overview of SSC

Given a set of points drawn from a union of linear or affine subspaces, the task is to find segmentation of the data. Let { S₁, ..., S_n } be an arrangement of n linear subspaces of dimensions { d₁, ..., d_n } embedded in D dimensional space. Consider a given collection of N = &sum _i N_i data points { y₁, ..., y_N } drawn from the n subspaces. The sparse subspace clustering (SSC) algorithm addresses the subspace clustering problem using techniques from sparse representation theory. This algorithm is based on the observation that each data point y in S_i can always be written as a linear combination of all the other data points in { S₁, ..., S_n }. However, generically, the sparsest representation is obtained when the point y is written as a linear combination of points in its own subspace. It is shown that when the subspaces are low-dimensional and independent (dimension of the sum is equal to the sum of dimensions), this sparse representation can be obtained by using L₁ minimization. The segmentation of the data is found by applying spectral clustering to a similarity graph formed using the sparse coefficients.

Theorem (Elhamifar & Vidal 2009)

For data points drawn from a union of independent linear subspaces, a subspace-sparse representation can be found by solving the following convex program.

D is the dictionary formed from the data points as the data is self expressive. For data lying in independent affine subspaces, we have an addition constraint that columns of C should add to 1.

Challenges with Anomaly Segmentation

Since SSC algorithm needs interesting points from a video frame, we compute the keypoints using SURF features for the first video frame. These points are then tracked using KLT (Kanade-Lucas-Tomasi) Tracker for rest of the frames to obtain a point lying in N dimensional euclidean space, N being the number of frames. The convex problem is solved using Alternating Direction Method of Multipliers (ADMM) with LASSO.

A limitation with SSC is that it needs the number of subspaces beforehand to cluster the points. In the case of anomaly detection, this number is not fixed. It can be either 2 (if no anomaly present) or 3 (in presence of 1 anomaly). To overcome this issue, we use self-tuning clustering approach (Manor & Perona 2005). It iterates through the available options for the number of subspaces and selects the one which provides the minimum variance.

Results

SSC was applied to two anomalous videos. The clustered points in same color lie in the same subspace. It can be easily seen that an anomaly (bicycle or skateboard) has different colored points on it, specifying that it lies in a different subspace than the normal objects and the background. Another advantage for this approach is that it doesn't require any training as against RPCA combined with feature detection.