Olusegun Oshin
email: o.oshin@surrey.ac.uk

Andrew Gilbert
email: a.gilbert@surrey.ac.uk

John Illingworth
email: j.illingworth@surrey.ac.uk

Richard Bowden
email: r.bowden@surrey.ac.uk

Spatio-temporal Feature Recogntion using Randomised Ferns

In this paper we present a generic classifier for detecting spatio-temporal feature points within video. The premise being that given a feature detector, we can learn a classifier that duplicates its functionality which is both accurate and computationally efficient. This means that feature point detection can be achieved independent of the complexity of the original interest point formulation. We extend the naive Bayesian classifier of Ferns to the spatio-temporal domain and learn classifiers that duplicate the functionality of common spatio-temporal interest point detectors. Results demonstrate accurate reproduction of results with a classifier that can be applied exhaustively to video at frame-rate, without optimisation, in a scanning window approach.

Introduction

This paper presents an approach to learning a classifier capable of accurately and efficiently detecting spatio-temporal interest points in constant time for use in action recognition. Recognising actions in videos is a popular area in the field of computer vision. The task is complex because detectors need to be able to account for occlusion, cluttered backgrounds, camera motion, scale and illumination changes, and geometric variations in videos. Building upon the success of interest point detection in object recognition, one of the current approaches to the problem involves extracting local spatio-temporal interest points and encoding them using descriptors that are robust to the variations mentioned above. These interest points are local regions that possess high information content. They are usually areas of large local variations in pixel intensity. In 2D images these changes are observed in the spatial dimension. For videos however, temporal variations also have to be considered.

We propose a general framework for training interest point detectors in video, such that, given examples of the type of interest point within a training video, we can detect those feature types at near frame rate in a novel video sequence. We extend a Naive Bayesian classifier called Ferns [START_REF] Ozuysal | Fast keypoint recognition in ten lines of code[END_REF] to the spatio-temporal domain and show that we are able to recognise chosen spatio-temporal features quickly and reliably. Our work is motivated by the use of ferns in rapidly classifying keypoints in 2D images while maintaining high classification rates.

We test our method by comparing its ability to reproduce the functionality of popular spatio-temporal interest point detectors proposed by Laptev and Lindeberg [START_REF] Laptev | Space-time interest points[END_REF] and Dollar et al [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF]. The key contributions of this paper are the extension of the Fern classifier to the spatio-temporal domain, hence encoding temporal information of features without increasing computational overhead; and a generic approach to recognising spatio-temporal features efficiently in constant time regardless of original detector complexity.

The layout of the rest of this paper is as follows. Section 2 summarises related work. Section 3 explains how ferns are extended to the spatio-temporal domain. Section 4 presents experimental results from training with two detection algorithms. Finally, section 5 concludes the paper.

Related research

An example of a simple spatial interest point detector is the corner detector developed by Harris and Stephens [START_REF] Harris | A combined corner and edge detection[END_REF], which has been used in many applications involving object matching and tracking. Schmid and Mohr [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF] proposed a rotationally invariant local image descriptor at each interest point that has been successful in image indexing. Lowe [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] introduced the SIFT descriptor, which is invariant to scale as well as rotation and translation, but only partially invariant to affine projection and changes in illumination. SIFT has proven effective in many areas as its invariance has underpinned recent trends into large scale object recognition. More recently, considerable effort has gone into the development of affine invariant detectors. An extended evaluation of interest point detectors can be found in [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF].

Similarly, in the spatio-temporal domain, interest points are proving to be important in activity recognition. Laptev and Lindeberg [START_REF] Laptev | Space-time interest points[END_REF] extended the Harris Corner detector to include corners in time, where a spatio-temporal corner is essentially a spatial corner exhibiting non-constant motion in time. Dollar et al [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF] argue that the direct extension of spatial interest point detectors to the spatio-temporal domain does not provide a sufficient method of detecting spatiotemporal features. They found that spatio-temporal features were too sparse so they proposed a method of detecting local features that would maximise discrimination between actions. Other methods based on local features include [START_REF] Schuldt | Recognizing human actions: A local SVM approach[END_REF], [START_REF] Niebles | Unsupervised learning of human action categories using spatial-temporal words[END_REF] and [START_REF] Oikonomopoulos | Spatiotemporal salient points for visual recognition of human actions[END_REF].

In contrast to the above local detection methods, Ke et al [START_REF] Ke | Efficient visual event detection using volumetric features[END_REF] and Cooper and Bowden [START_REF] Cooper | Sign language recognition using boosted volumetric features[END_REF] generalise integral images [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF] to an efficient space-time representation called an integral volume, allowing for global classification. They use volumetric features which are box volumes reminiscent of the Haar-basis features used by Viola and Jones [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF]. Ke et al use a sliding volume over the entire video, as an extension of [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF] to 3D and build a real time event detector that uses dense optical flow measurements to recognise actions. Other global approaches include [START_REF] Efros | Recognizing action at a distance[END_REF], [START_REF] Shechtman | Space-time behavior-based correlation[END_REF] and [START_REF] Wong | Extracting spatiotemporal interest points using global information[END_REF].

Of particular relevance is the work of Lepetit et al [START_REF] Lepetit | Keypoint recognition using randomized trees[END_REF], in which they treat wide baseline matching of feature points in images as a classification problem and define a class as the set of all possible views of a particular keypoint. They use Randomised Trees to rapidly match keypoints in images and classify images. Already widely used in character recognition, each node of a randomised tree contains a simple test which eventually decides the leaf distribution. To increase the speed of randomised trees Ozuysal et al [START_REF] Ozuysal | Fast keypoint recognition in ten lines of code[END_REF] proposed the fern classifier. Ferns are non-hierarchical structures that have been shown to achieve excellent classification rates while reducing computational overhead.

Method

We aim to detect spatio-temporal features accurately and efficiently in video using a semi-naive Bayesian classifier called Ferns, proposed in [START_REF] Ozuysal | Fast keypoint recognition in ten lines of code[END_REF], as an alternative to Randomised Trees [START_REF] Lepetit | Keypoint recognition using randomized trees[END_REF]. We learn ferns on regions surrounding spatio-temporal features, which are detected using a spatio-temporal feature detector. In this section we give an overview of the methods used and how they are combined for the training and classification of actions in new videos. Randomised Trees are simple yet effective classification structures that have been used in handwriting recognition [START_REF] Amit | Shape quantization and recognition with randomized trees[END_REF] and applied to object recognition [START_REF] Lepetit | Keypoint recognition using randomized trees[END_REF]. All non-leaf nodes of a randomised tree contain a simple test that splits the space of the data to be classified. Lepetit and Fua [17] used the simple test of comparing pixel intensities, which could be chosen randomly or by a greedy algorithm that gives the best separation based on information gain. After training, the leaf nodes contain estimates of the posterior distributions over the classes that an image reaches that leaf. Randomised trees are built in a top-down manner and all training examples are passed down the tree through nodes based on the test. Figure 1 shows a randomised tree that uses a comparison of pixel intensities as the test. If the intensity at point j 1 of the image patch is greater than that of point j 2 , then the patch is passed down the tree via the right child node; otherwise, it traverses the left child node. The process terminates when the node receives too few examples or it reaches a given depth. It would be very difficult to build one tree that performs well for a large number of classes, training examples and possible tests, so multiple trees are grown, and each tree is trained with a random subset of the training examples to obtain weak dependency between the trees. When classifying, a test patch is passed down each of the trees to a leaf node. The class assigned to the image is found by averaging the posterior distributions at the node of each tree where the image terminates, and the class with the maximum value is selected. Ferns [START_REF] Ozuysal | Fast keypoint recognition in ten lines of code[END_REF], unlike randomised trees, are non-hierarchical structures. Each fern consists of a set of ordered binary tests and returns the probability that a patch belongs to each of the classes learnt during training. The structure of ferns is shown in Figure 2. Each node in a fern returns a binary digit based on the result of the test. Hence, a fern with S nodes will return a number between 0 and 2 S -1. For multiple patches that belong to the same class, the output of a fern for that class can be modelled with a multinomial distribution. During classification, performing the set of tests on a test patch also returns a binary code, which is used to obtain the likelihood of occurrence in each class. The class is found by multiplying class probabilities across the ferns, and selecting the class that gives the maximum product. Performance-memory trade-offs can be made by changing the size and number of ferns allowing for flexible implementation. We follow the method of Ferns described above and extend it to spatiotemporal neighbourhoods centered at feature points called cuboids [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF]. The sets of binary tests we perform on the cuboids are not single pixel comparisons. Instead, we have defined a node as a comparison between the sums of two normalised subpatches. These are random sized patches that fit within the spatial area of the cuboid. The locations in space and time are also chosen randomly. Figure 3 shows a flattened spatio-temporal volume with subpatches generated on different frames within the volume. Hence for subpatches encoded by a spatial offset x, y, spatial extent x s , y s and temporal offset t, a node is a simple comparison:

Randomised Trees and Ferns

Semi-Naive Bayesian Spatio-temporal Classification

f j = 1 if s(x 1 , y 1 , x s1 , y s1 , t 1 ) < s(x 2 , y 2 , x s2 , y s2 , t 2 ); 0 otherwise.
where s is the sum of a subpatch, given by

s(x, y, x s , y s , t) = 1 x s y s x+xs x ′ =x y+ys y ′ =y I(x ′ , y ′ , t).
The sums are normalised by the number of pixels in the subpatch, x s y s . We make use of sum of subpatch comparisons as opposed to pixel comparisons so as to build a classifier that is more robust to scale variations.

Training

Given a cuboid belonging to a particular class, we train a fern classifier by generating S nodes as described above. We perform the node tests and obtain values f j , where j = {1 . . . S}, for each fern. All the node results {f 1 , f 2 , . . . , f S } are combined to form a binary code, which is then converted to decimal. For a set of cuboids belonging to the same class, we build a histogram of the decimal values, and normalise it to give a probability distribution for that class. For additional classes, the same tests are performed within the fern and separate distributions are obtained for them. Multiple ferns are trained by generating new nodes and obtaining distributions for all classes within the ferns.

In order to rapidly calculate the difference between the sums of subpatches, we calculate the integral image representation [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF] of each frame in the cuboid. We choose to use integral images of each frame as opposed to an integral volume of the cuboid because the volumetric approach adds an additional parameter. Laptev and Perez [START_REF] Laptev | Retrieving actions in movies[END_REF] investigated the use of a classifier trained on a single keyframe of drinking actions. They bootstrap a space-time classifier and apply it to the keyframes, and have shown that this method of combining shape and motion information gives significant improvement in detection performance.

Classification

To classify a new cuboid, we apply the fern classifier by performing the same set of ordered node tests on the cuboid as we did during training, and obtain a decimal value from the combined binary node results. The decimal value determines the bin of the class distributions within the fern that is selected. For a single fern, the cuboid most likely belongs to the class that has the highest value in the selected bin. For multiple ferns, we combine the selected bin values within the classes and across the ferns, assuming independence between the distributions. We select the class that has the maximum likelihood.

Results

We train and test our algorithm on the KTH video data set [START_REF] Schuldt | Recognizing human actions: A local SVM approach[END_REF], which contains videos of 25 persons performing six actions in four different scenarios. These actions are boxing, hand waving, walking, running, jogging and hand clapping. The videos are taken over static homogenous backgrounds and are split into four different conditions that include scale variations, different clothes and lighting changes. Of the 25, 8 persons are used for training, 9 for testing, and the remainder for validation purposes as outlined in the data set. Although the KTH Data set is limited in terms of complexity, it is important to note that our intention is to provide comparable interest point segmentation to other detectors and not to classify the actions.

We evaluate against two different feature point detectors and try to obtain comparable detection performance. Having trained the classifier, testing is done using each one of the test videos. We present our detector's ability to recognise learnt features in the video using a scanning volume over the entire test video sequence. The feature point detectors used are described in the next section. The first is an extension of the Harris corner detector [START_REF] Harris | A combined corner and edge detection[END_REF] to the spatio-temporal domain by Laptev and Lindeberg [START_REF] Laptev | Space-time interest points[END_REF], selecting local maxima of spatio-temporal corners as features. In our results this method is labelled Laptev. The second method by Dollar et al [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF] applies separable linear filters to the video and selects local maxima of the response as features, labelled Dollar. Laptev and Lindeberg [START_REF] Laptev | Space-time interest points[END_REF] extend the Harris corner detector [START_REF] Harris | A combined corner and edge detection[END_REF] to the spatiotemporal domain by requiring that image values in space-time have significant variations in the spatial and temporal dimensions. Hence these spatio-temporal corners are spatial corners exhibiting non-constant motion in a spatio-temporal neighbourhood. They compute a windowed 3 × 3 second moment matrix composed of first order spatial and temporal derivatives, averaged with a Gaussian weighting function. Interest points are then detected by searching for regions that have significant eigenvalues of the matrix.

Feature Point Extraction

The second method, proposed by Dollar [START_REF] Dollár | Behavior recognition via sparse spatio-temporal features[END_REF], applies separable linear filters to the video sequence. A response function of the form R = (I * g * h ev ) 2 + (I * g * h od ) 2 is obtained, where g(x, y : σ) is the 2D Gaussian kernel applied along the spatial dimensions of the video and h ev and h od are a quadrature pair of 1D Gabor filters applied in the temporal dimension. The detector responds best to complex motions made by regions that are distinguishable spatially, including spatio-temporal corners as defined by [START_REF] Laptev | Space-time interest points[END_REF], but not to pure translational motion or motions involving areas that are not distinct in space. Local maxima of the response function R are selected as interest points, and cuboids are extracted, which are the windowed pixel values around the interest point in the spatial and temporal dimensions.

For both methods, the scale at which an event is observed determines the type of event that is detected, so interest points are computed at different spatiotemporal scales.

Performance

During training, we apply the classifier to the extracted volumes surrounding each of the feature points detected. Figure 4 highlights detected feature points in a video. We detect features at one spatial and temporal scale. Ideally, training should be done at different spatio-temporal scales and the scanning volume applied over a range of scales, but we show that our classifier is able to handle scale changes. Once feature volumes are extracted, we artificially generate additional positive example cuboids by randomly offsetting and scaling the cuboids at the detected feature points by a small amount in all directions, making our classifier robust to slight variations in the feature regions. We then create a class of negative example cuboids, which are extracted at randomly selected areas that do not overlap with feature cuboids. The number of background cuboids and the number of feature cuboids are equal to avoid biasing the classifier. The number of ferns and the number of nodes in each fern are parameters that can be varied to achieve a trade-off between memory and performance. For our tests we generate 50 ferns with 3 nodes.

In order to detect features in a new video we make use of a spatio-temporal scanning window across the video. We then apply the ferns classifier on the region within the window to determine whether it is a feature or background. The subpatch comparisons are done efficiently by using an integral image representation [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF] of the entire video, which is calculated once. This differs from the integral video used in [START_REF] Ke | Efficient visual event detection using volumetric features[END_REF] as the integral images are computed on each frame of the video separately. The sums of patches selected can therefore be computed using 4 array dereferences, giving 8 array dereferences for each node comparison. The scanning window operates over alternate pixels and frames to reduce classification time without loss of accuracy (the random noise added during training which gives robustness to offsets from the optimal detection position).

To determine whether the windowed volume contains a feature, we find the log likelihood ratio that the cuboid contains a feature to background. Receiver Operating Characteristic (ROC) Curves are used to determine how well the classifier is able to emulate the detections learnt during training. Positives in our data are feature cuboids detected by the feature detector prior to training, and true positives are positives that have also been labelled a feature by our classifier. The ROC curve is obtained by varying the threshold on the likelihood ratio.

We expect our classifier to trigger multiple detections around a positive and that the detections will not always occur at the same points selected by the feature detectors. This is natural as noise was added during training. To this end, we choose a minimum percentage by which a cuboid classified as a feature must overlap an actual detected feature before it can be labelled a true positive. Figure 5 shows averaged ROC curves obtained for different percent overlaps. All percent overlaps perform well, with 100% overlap having a surprisingly good Equal Error Rate of approximately 0.65. For our experiments we deemed 50% overlap fair. Figure 6 shows how well we are able to detect learnt features in a novel video sequences. Each curve indicates the different scenarios of the KTH video data set [START_REF] Schuldt | Recognizing human actions: A local SVM approach[END_REF], where S1 is static with a homogenous background, S2 includes scale variations, S3 is performed with different clothing, and S4 has illumination variations. We display results for Boxing, Handwaving and Walking for both feature point detectors. It can be seen that the spatio-temporal fern classifier performs extremely well in detecting learnt features. It is able to correctly recognise more than 95% of the Dollar features with less than 5% error for all the scenarios. For Laptev features, we obtain Equal Error Rates of approximately 90% for the actions in all scenarios except for Illumination variations (S4), where the Equal Error Rates are roughly 85% for Boxing and Walking features. This lower performance on the Laptev features is not surprising as these features are more localised than those of Dollar and the spatial-temporal volume the ferns operate upon incorporates additional surrounding information. We kept the classifier the same between both experiments to allow comparison, but optimising the spatiotemporal support region of the classifier for different features is likely to increase performance further. It is worth noting that although the classifier was trained at one spatial and temporal scale, the S2 curves show that performance on different scales is comparable to that of the static homogenous background. This highlights the classifier's ability to cope with changes in scale from the training data. To further assess generality, we investigated the ability of our classifier to 6 detect from one action, features learnt from other actions. This test relies upon the original features being invariant to action type as well occurring in both activities, which although desirable, might be assumed is not the case. Having trained the classifier on Boxing features, we test its ability to detect features that occur in a Walking video sequence and present the results in Figure 7. It can be seen that features common to Boxing and Walking are detected with high equal error rates, showing that irrespective of the action, the classifier gives good performance in detecting spatio-temporal features. This also goes some way to demonstrating that the features are indeed consistent and invariant to the action performed.

The Dollar detector runs at frame rate on the KTH data which is impressive despite its matlab implementation. The Laptev detector is considerably slower to apply, but again, this is a matlab implementation and could undoubtedly be sped up through optimisation. Our classifier was implemented in C++ and using the scanning window approach also achieves frame rate processing on the KTH data. However, the speed of the classifier is dependent upon the number of Ferns and nodes used for classification. With optimisation, similar classification performance could be achieved with less ferns and future work will investigate this optimisation. Furthermore, Ferns can be structured so that a low cumulative likelihood early in classification is rejected without applying the entire classifier.

Conclusion

We extended the Semi-Naive Bayesian classifier to the spatio-temporal domain and proposed a generic approach to recognising spatio-temporal features. The method is demonstrated on the task of detecting learnt spatio-temporal features on the KTH video data set. We presented results of detection having trained on features selected by two different spatio-temporal feature point detectors and show the ability of the classifier to obtain results comparable to these feature detectors on test data. These high classification rates are achieved in constant time without an increase in computational overhead.

Fig. 1 .

 1 Fig. 1. A Randomised Tree using pixel intensity comparisons at random points in the image patch. After training, each leaf node contains class probabilities of a new patch arriving at that node.

Fig. 2 .

 2 Fig. 2. A set of ferns. The binary digits are results of the comparison between pixels at points j 1 and j 2 . During training, an image patch belonging to a particular class is run through all nodes in all ferns and each fern updates its distribution for that class based on the results. During classification, the results are used to select bins in the class histograms.

Fig. 3 .

 3 Fig. 3. Example of nodes in the spatio-temporal domain. The cuboid is flattened with respect to time to show subpatches at different temporal offsets.

Fig. 4 .

 4 Fig. 4. Example frames from action video sequences highlighting points where spatiotemporal features have been detected. These points are used as positive data during training.

Fig. 5 .

 5 Fig. 5. Classification of features against background for various percentages of overlap between classified feature cuboids and actual positive feature cuboids

  Left: ROC Curves for features detected by the Dollar feature detector against background for Boxing, Handwaving and Walking. Right: ROC Curves for features detected by the Laptev feature detector against background for Boxing, handwaving and Walking. Each graph shows performance in the four scenarios of the KTH video data set, S1 -S4, where S1 videos have a static homogenous background, S2 have scale variations, subjects in S3 have different clothes, and S4 have illumination variations. ROC curves for features detected in Walking video sequences trained with Boxing features. S1 to S4 are defined as in Figure

				ROC Curves for detecting Features in Walking videos, trained with Boxing features
				1
				0.9
			ROC Curves for detecting Dollar Boxing Features against background 0.8			ROC Curves for detecting Laptev Boxing features against
			for scenarios S2 to S4			background for scenarios S1 to S4
		1		0.7		1
	True Positive Rate	0.7 0.75 0.8 0.85 0.9 0.95	True Positive Rate	0.2 0.3 0.4 0.5 0.6 0.1	True Positive Rate	0.7 0.75 0.8 0.85 0.9 0.95	S1 S2 S3 S4
	0 0 0 Fig. 6. 0 0.05 0.1 0.15 0.2 0.25 0.3 0.5 0.55 0.6 0.65 False Positive Rate 0.05 0.1 0.15 0.2 0.25 0.3 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 False Positive Rate True Positive Rate ROC Curves for detecting Dollar Handwaving Features against 0.35 0.4 0.45 S1 S2 S3 S4 0.35 0.4 0.45 background for scenarios S1 to S4 S1 S2 S3 S4 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 False Positive Rate True Positive Rate ROC Curves for detecting Dollar Walking Features against background for scenarios S1 to S4 S1 S2 S3 S4 0.1 0.2 0.3 0 Fig. 7.	0.5 0.5 0.5 0.4 False Positive Rate True Positive Rate True Positive Rate 0.5 0.6	0 0 0 0.7 0.5 0.55 0.6 0.65 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1	0.05 0.05 ROC Curves for detecting Laptev Handwaving Features against 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 False Positive Rate S1 S2 S3 S4 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 False Positive Rate background for scenarios S1 to S4 S1 S2 S3 S4 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 False Postive Rate ROC Curves for detecting Laptev Walking Features against background for scenarios S1 to S4 S1 S2 S3 S4 0.8 0.9 1	0.5 0.5 0.5


Louis Kratz

Ko Nishino

Spatio-Temporal Motion Pattern Modeling of Extremely Crowded Scenes

The abundance of video surveillance systems has created a dire need for computational methods that can assist or even replace human operators. Research in this field, however, has yet to tackle an important real-world scenario: extremely crowded scenes. The excessive amount of people and their activities in extremely crowded scenes present unique challenges to motion-based video analysis. In this paper, we present a novel statistical framework for modeling the motion pattern behavior of extremely crowded scenes. We construct a rich yet compact representation of the local spatio-temporal motion patterns and model their temporal behaviors with a novel, distribution-based Hidden Markov Model (HMM), exploiting the underlying statistical characteristics of the scene. We demonstrate that, by capturing the steady-state behavior of a scene, we can naturally detect unusual events as unlikely motion pattern variations. The experiments show promising results in extremely crowded real-world scenes with complex activities that are hard for even human observers to analyze.

Introduction

Despite the general interest and active research in motion-based video analysis, an important area of video surveillance has been left widely untackled. Extremely crowded scenes, as shown in Fig. 1, are perhaps in the most need of computational methods for analysis. Crowded, public areas require monitoring of an extreme number of individuals and their activities, a significant challenge for even a human observer. Videos with this level of activity have yet to be analyzed via computational methods. Common video analysis scenes, such as the PETS 2007 database [START_REF]PETS: Tenth IEEE Int'l Workshop on Performance Evaluation of Tracking and Surveillance[END_REF], contain less than one hundred individuals in even the most crowded samples. Extremely crowded scenes contain hundreds of people in any given frame, and possibly thousands through the duration of the video.

As illustrated in Fig. 1, the people and objects that compose extremely crowded scenes present an entirely different level of challenges due to their excessive quantity and complex activities. Moving pedestrians can undergo drastic appearance changes between frames, and their sheer number consistently causes excessive local and global occlusions. These characteristics make traditional motion-based approaches such as tracking and segmentation extremely difficult, if not impossible.

In this paper, we derive a novel motion pattern framework for analyzing videos of extremely crowded scenes. Our key insight is to exploit the excessive motion patterns within local areas of the entire sequence, modeling the underlying intrinsic structure they form in the video. In other words, we model the motion variation in local space-time volumes and their temporal statistical behaviors that characterize the scene. Our construction is unique in that it captures the large motion pattern variations in the video sequence while maintaining a robust representation of the motion in local video regions. To capture the typical motion behaviors of the scene, we derive a distribution-based HMM that retains the rich motion information within our local spatio-temporal motion pattern representation and describes natural motion transitions within a local video region. We use this to model the stationary structure of motion patterns in the video, i.e. usual events within the scene, and identify atypical events as statistical anomalies.

We capture the excessive motion within the scene by dividing the video into spatio-temporal volumes of a fixed size, which we refer to as cuboids, to represent the local motion behavior. We encode the rich motion patterns in each cuboid with a multivariate Gaussian distribution of its 3D spatio-temporal gradients. Furthermore, we identify prototypical motion patterns in disjoint spatio-temporal locations, providing a faithful yet compact representation of the scene's motion characteristics. Based on these representations, we derive a novel distribution-based HMM that fully utilizes the motion pattern representations, multivariate Gaussian distributions, to characterize their temporal variations. Distribution-based HMMs provide the flexibility to model the motion pattern variations directly from the representation by handling observations that are distributions themselves. The entire video volume is thus modeled as a collection of distribution-based HMMs that encodes the intrinsic statistical structure of local spatio-temporal motion patterns. We model a crowded scene given a training video sequence of usual activity, and detect unusual activities in a query video by identifying local spatio-temporal motion patterns with low likelihoods. To our knowledge, this is the first work to model the motion patterns of truly crowded scenes and successfully detect unusual activities in them.

Relation to Previous Work

Motion-based video analysis has been an active and popular field of research, using various techniques to represent motion characteristics depending on the application. Here we review previous work that focuses specifically on motionbased analysis of crowded scenes and unusual event detection.

Approaches to unusual event detection can be categorized into two groups: event detection and deviation methods. Deviation approaches model usual activity, detecting unusual events as those that differ from the model [START_REF] Hu | A System for Learning Statistical Motion Patterns[END_REF][START_REF] Dee | Detecting Inexplicable Behaviour[END_REF][START_REF] Cui | A Sequential Monte Carlo Approach to Anomaly Detection in Tracking Visual Events[END_REF][START_REF] Zhou | Unusual Event Detection via Multi-camera Video Mining[END_REF][START_REF] Xiang | Online Video Behaviour Abnormality Detection Using Reliability Measure[END_REF][START_REF] Salas | A Double Layer Background Model to Detect Unusual Events[END_REF][START_REF] Zhong | Detecting Unusual Activity in Video[END_REF][START_REF] Andrade | Modelling Crowd Scenes for Event Detection[END_REF][START_REF] Boiman | Detecting Irregularities in Images and in Video[END_REF][START_REF] Adam | Robust Real-Time Unusual Event Detection using Multiple Fixed-Location Monitors[END_REF]. Event detection approaches explicitly model specific activities for identification in query videos [START_REF] Chan | Detecting Rare Events in Video Using Semantic Primitives with HMM[END_REF][START_REF] Gryn | Detecting Motion Patterns via Direction Maps with Application to Surveillance[END_REF][START_REF] Johnson | Learning the Distribution of Object Trajectories for Event Recognition[END_REF]. These have the capability of differentiating between detected events, however modeling each possible event in extremely crowded scenes is unfeasible. The number of events required to robustly capture the large variability of usual activity in extremely crowded scenes would be substantial. On the other hand, the large amount of activity in extremely crowded scenes provides an abundance of data representing the stationary behavior of the scene's constituents, i.e. the usual activities, making a deviation approach suitable.

Motion-based video analysis approaches model the deviation of motion characteristics throughout the video volume. Trajectory-based approaches [START_REF] Hu | A System for Learning Statistical Motion Patterns[END_REF][START_REF] Dee | Detecting Inexplicable Behaviour[END_REF][START_REF] Chan | Detecting Rare Events in Video Using Semantic Primitives with HMM[END_REF][START_REF] Johnson | Learning the Distribution of Object Trajectories for Event Recognition[END_REF], for example, track scene objects, describing the motion by a change in spatial location, and spatial deviations are considered unusual. Trajectory-based techniques are suitable for scenes with few moving objects that can easily be tracked, such as infrequent pedestrian or automobile traffic. The tracking challenges posed by extremely crowded scenes, however, makes trajectory-based representations unfeasible. In addition, the motion analysis of trajectory-based approaches focuses on each subject individually, but the behavior of extremely crowded scenes depends on the motion of multiple subjects concurrently.

Other motion pattern approaches [START_REF] Black | Explaining Optical Flow Events with Parameterized Spatio-Temporal Models[END_REF][START_REF] Andrade | Modelling Crowd Scenes for Event Detection[END_REF][START_REF] Boiman | Detecting Irregularities in Images and in Video[END_REF][START_REF] Ke | Event Detection in Crowded Videos[END_REF][START_REF] Dementhon | Video Retrieval using Spatio-Temporal Descriptors[END_REF][START_REF] Chomat | Probabilistic Recognition of Activity using Local Appearance[END_REF][START_REF] Dollar | Behavior Recognition via Sparse Spatio-Temporal Features[END_REF][START_REF] Laptev | Velocity Adaptation of Spatio-Temporal Receptive Fields for Direct Recognition of Activities: An Experimental Study[END_REF] model the spatio-temporal volume directly. These approaches often estimate the optical flow [START_REF] Black | Explaining Optical Flow Events with Parameterized Spatio-Temporal Models[END_REF][START_REF] Andrade | Modelling Crowd Scenes for Event Detection[END_REF] or the motion within spatio-temporal volumes [START_REF] Boiman | Detecting Irregularities in Images and in Video[END_REF][START_REF] Ke | Event Detection in Crowded Videos[END_REF][START_REF] Dementhon | Video Retrieval using Spatio-Temporal Descriptors[END_REF][START_REF] Dollar | Behavior Recognition via Sparse Spatio-Temporal Features[END_REF]. Flow-based approaches have modeled motion deviations in the form of HMMs [START_REF] Andrade | Modelling Crowd Scenes for Event Detection[END_REF] or Baye's classifiers [START_REF] Black | Explaining Optical Flow Events with Parameterized Spatio-Temporal Models[END_REF] to represent sparse human motion. Unfortunately, the excessive number of subjects present in extremely crowded scenes make the estimation of optical flow unreliable. Furthermore, the variation of activities caused by the large number of individuals makes specific behavior difficult to define and isolate. The nature of extremely crowded scenes, however, requires the ability to capture activity within local scene regions. Extremely crowded scenes may contain any number of concurrent, independent activities taking place in different local areas of the same sequence. This makes global approaches, such as full frame analysis [START_REF] Zhong | Detecting Unusual Activity in Video[END_REF][START_REF] Andrade | Modelling Crowd Scenes for Event Detection[END_REF], unfeasible, as the entire frame would be dominated with visual information irrelevant to the specific event of interest.

Spatio-temporal approaches [START_REF] Boiman | Detecting Irregularities in Images and in Video[END_REF][START_REF] Ke | Event Detection in Crowded Videos[END_REF][START_REF] Dementhon | Video Retrieval using Spatio-Temporal Descriptors[END_REF][START_REF] Dollar | Behavior Recognition via Sparse Spatio-Temporal Features[END_REF] directly represent the motion patterns within video volumes. Though these motion pattern representations are well suited to extremely crowded scenes, the modeling of their behavior has been limited to volume distance [START_REF] Ke | Event Detection in Crowded Videos[END_REF][START_REF] Boiman | Detecting Irregularities in Images and in Video[END_REF] or interest points [START_REF] Dollar | Behavior Recognition via Sparse Spatio-Temporal Features[END_REF], requiring the explicit modeling of each event to be detected. In addition, most spatio-temporal representations assume that the volume contains a dominant, uniform motion. In extremely crowded scenes, it is exactly the non-uniform motion patterns that characterize the crowd behavior. The nature of extremely crowded scenes, specifically the high concentration and large variability of motion patterns, makes previous motion pattern approaches unsuitable for activity analysis. Other approaches such as statistical background modeling [START_REF] Pless | Spatio-temporal Background Models for Outdoor Surveillance[END_REF][START_REF] Zhong | Segmenting Foreground Objects from a Dynamic Textured Background via a Robust Kalman Filter[END_REF] also fail on extremely crowded scenes as the large number of people often completely occlude the background, making the foreground and background indistinguishable. The large amount of motion present in the scene, however, lends itself naturally to a volumetric-based approach, but requires a robust handling of non-uniform motion patterns and a flexible model to capture large motion variations. The construction of a canonical representation of motion patterns within the video sequence is a challenging problem that we explore via the use of novel distribution-based HMMs. The strict motionpattern requirements presented by extremely crowded scenes makes a direct comparison of our approach to previous work unsuitable, as previous models do not capture large motion pattern variations in local areas of the video scene.

Local Spatio-Temporal Motion Patterns

Extremely crowded scenes contain large amounts of independent, local activities. Yet these local activities in the space-time form an underlying intrinsic structure that exhibits characteristic motion patterns and variations in the video. Our goal is to derive a compact representation of the motion patterns that remains faithful to the scene behavior, and provides means to model their temporal variations.

Spatio-Temporal Motion Representation

We represent the video as a collection of local spatio-temporal volumes as shown in Fig. 2(a) by subdividing the video into volumes of fixed size. The set of non-uniform motion patterns encoded in these cuboids collectively forms the complex motion in the entire video volume. A finer-grain representation, such as optical flow, would not provide enough motion information. Conversely, the motion of the entire frame would not provide the level of detail necessary for differentiating between independent, concurrent activities. By dividing the video into spatio-temporal volumes, we can extract robust motion information while isolating separate activities to local regions.

We wish to represent the rich, non-uniform, local spatio-temporal motion patterns encapsulated in each cuboid in a compact yet faithful manner. We use the distribution of spatio-temporal gradients as our base representation. For each pixel i in cuboid I, we calculate the spatio-temporal gradient ∇I i

∇I i = [I i,x I i,y I i,t ] T = ∂I ∂x ∂I ∂y ∂I ∂t T , (1)
where x, y, and t are the video's horizontal, vertical, and temporal dimensions. The set of spatio-temporal gradients from each pixel represents the characteristic motion pattern encoded within the cuboid.

As illustrated in Fig. 2(b), we model the distribution of gradients as a 3D Gaussian distribution N (µ, Σ) where

µ = 1 N N i ∇I i , Σ = 1 N N i (∇I i -µ)(∇I i -µ) T . (2)
Thus for each spatial location n and temporal location t, the local spatiotemporal motion pattern representation O n t is defined by µ n t and Σ n t . This representation has been used previously for background modeling [START_REF] Pless | Spatio-temporal Background Models for Outdoor Surveillance[END_REF], and is similar to the Gram Matrix used for analyzing persistent motion patterns [START_REF] Wright | Analysis of Persistent Motion Patterns Using the 3D Structure Tensor[END_REF] and correlating video sequences [START_REF] Shechtman | Space-Time Behavior Based Correlation[END_REF]. The explicit multivariate Gaussian modeling allows us to derive sound statistical temporal models for analyzing pattern variations while faithfully capturing the multiple non-uniform motion encoded in the cuboid.

Distance Metric

Given a compact representation of the local spatio-temporal motion pattern, we need a canonical distance metric to measure the difference between cuboids in subsequent modeling of the video. Previous approaches have used algebraic metrics which are sensitive to noise [START_REF] Nishino | Clustered Blockwise PCA for Representing Visual Data[END_REF], or assume that the cuboid volume only consists of a uniform motion [START_REF] Shechtman | Space-Time Behavior Based Correlation[END_REF][START_REF] Ke | Event Detection in Crowded Videos[END_REF]. We use an information theoretic distance metric that directly measures the distribution distances: the symmetric Kullback-Leibler (KL) divergence [START_REF] Kullback | On Information and Sufficiency[END_REF]. Since we model the spatio-temporal motion patterns as Gaussian distributions, the divergence has a closed analytical form [START_REF] Myrvoll | On Divergence Based Clustering of Normal Distributions and its Application to HMM Adaptation[END_REF], providing a solid, nonnegative comparison between motion patterns.

The symmetric KL distance measure contains the inverse of both covariance matrices. Cuboids with little or no motion and texture have small covariance matrices, introducing large errors in the KL distance. We define a less sensitive distance measure between two distribution A and B

d(A, B) = ( 0 K(Σa) > dK, K(Σ b ) > dK, Σa -Σ b F < dΣ, µ a -µ b < dµ d(A, B) otherwise , (3)
where d(A, B) is the KL Divergence and K() is the condition number of the matrix, confirming that the inverse is unstable. The norms of the covariance and mean differences are calculated to ensure that the distributions are within acceptable distances (d Σ , d µ ). We refer to this measure as the KL distance for the remainder of this paper.

Prototypical Local Spatio-Temporal Motion Patterns

By directly modeling the video as a collection of normal distributions, we reduce the size of the video representation from a set of raw pixels to a collection of Gaussian parameters. As illustrated in Fig. 2(c), we further reduce the size of this representation by exploiting common motion patterns occurring in disjoint space-time locations. We model the recurrence of similar motion patterns by extracting prototypical local spatio-temporal motion patterns (prototypes) that characterize the activities of the scene. Note that prototypical motion patterns can occur at disjoint spatio-temporal locations, and such recurrences actually form the usual activities of the scene. Many methods exist that can extract a video's prototypes. Off-line clustering techniques such as K-means, however, require that all of the observations be available. We use an online method that computes the KL distance from each local spatio-temporal motion pattern O n t to the prototypes as we parse the video. If the KL distance is greater than a specified threshold, d KL , for all prototypes {P s |s = 1, . . . , S}, then the cuboid is considered a new prototype. Otherwise, the prototype distribution P s is updated with the new observation O n t by

P s = 1 N s + 1 O n t + 1 - 1 N s + 1 P s , (4)
where N s is the total number of observations associated with the prototype P s at time t. To solve Eq. 4 with respect to the KL-divergence, we use the expected centroid presented by Myrvoll et al. [START_REF] Myrvoll | On Divergence Based Clustering of Normal Distributions and its Application to HMM Adaptation[END_REF] to compute the mean distribution P s . The use of the expected centroid provides an efficient way to compute prototypical representations that reflect the distance measure between motion pattern representations, ensuring a canonical calculation of motion patterns. By extracting prototypical local spatio-temporal motion patterns, we effectively construct a canonical representation of the video motion patterns. The local spatio-temporal motion patterns are classified by the prototypes, which represent the expected observed motion patterns within a specific KL distance. The variation in KL space between these observations describes the distribution of motion patterns associated with a prototype.

Statistical Characterization of Crowded Scenes

While the set of prototypes provides a picture of similar activities in the scene, it does not capture the relationship between their occurrences. By modeling the temporal behavior of local spatio-temporal motion patterns, we characterize a given video by its motion pattern variation. We assume that cuboids in the same spatial location exhibit Markov property in the temporal domain since the scene is comprised of physically moving objects. In order to achieve a localized model, we observe each spatial location separately creating a single HMM for each tube of observations in the video. However, since each cuboid is a distribution of gradients (3D Gaussian representing local motion patterns), and the video a collection of prototypes representing distributions of distributions, we must derive an HMM that can handle observations that are distributions themselves.

Distribution-Based Hidden Markov Models

Ordinary HMMs are defined by five parameters M = {H, o, b, A, π}, where H is the number of hidden states, o the possible values of observations, b a set of H emission probability density functions, π an initial probability vector, and A a transition probability matrix. We model a single HMM M n = {H n , O n , b n , A n , π n } for each spatial location n = 1, . . . , N and associate the hidden states H n with the number of prototypes S n in the tube. The set of possible observations O n is a continuous range of 3D Gaussian distributions. Complex observations for HMMs are often quantized for use in a discrete HMM. However, such quantization of observations would significantly reduce the rich motion information present in each cuboid. Our construction of distributionbased HMMs permits the observations to remain continuous 3D Gaussian distributions. Therefore, the emission probability density function for each prototype must be a distribution of distributions.

We model the local spatio-temporal motion pattern variation with a 1D normal distribution using the KL distance to remove the bias. Thus the probability of an observation

O n t is p(O t n |b s ) = p( d(O n t , P s ) σ s ) ∼ N (0, 1) , (5)
where P s is the average of the observed motion patterns assigned to prototype s, given in Eq. 4. This retains the rich motion information represented by each observation within the emission probability distribution, and provides a probability calculation consistent with our distance measure. The estimation of P s is given in Eq. 4 and the standard deviation by the maximum likelihood estimator

σ 2 s = 1 N s Ns j d(O j , Ps ) 2 , ( 6
)
representing the average KL distance between the mean distribution and observed motion patterns. In practice, however, there may be too few cuboids in a given classification to capture specific behavior with reliable variation. In such an occasion, we use a 99.7 percent window around d KL , letting σ s = 3d KL . This distribution-based HMM models the temporal behavior of local spatiotemporal motion patterns in a sound statistical framework. The emission probability distributions are created using Eq. 4 and 6 for each prototype in the scene. Note that, while a single HMM is computed for each tube, the emission probability density functions are created using samples from the entire video volume. The parameters A n and π n are estimated by expectation maximization.

Atypical Events as Statistical Anomalies

Modeling the temporal behavior of the local spatio-temporal motion patterns in a statistical framework provides a natural way to define usual activities as statistical stationary behavior. This in turn enables the detection of unusual events in the scene as statistical deviations from a learnt model of a video sequence that captures the mostly usual activities. Given a query video, the likelihood of a temporal sequence of local spatial-temporal motion patterns can be calculated via the forwards-backwards algorithm [START_REF] Rabiner | A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition[END_REF]. Let ζ n t be the likelihood of the t th temporal sequence of observations within a given video tube n. Thus

ζ n t = p(O n t , . . . , O n t+w |M n ) , (7)
where M n is the HMM at tube n, w is the sequence length, and O n t , . . . , O n t+w is the sequence of observed local spatio-temporal motion patterns. Ideally, we would like to focus this measure to each individual cuboid. Since ζ n t is calculated for every sequence within the tube of length w, each observation O n t is associated with w likelihood measures. We define an ensemble function that selects a measure from the set of likelihoods the observation contributed to. We use a window size of 2 and let the ensemble function maximize over the likelihoods. This correctly classifies the cuboids with the exception of one case, when a usual cuboid is temporally sandwiched between two unusual cuboids, which is rare and errs on the side of caution (a false positive). Observations with a likelihood less than a threshold ξ n are considered unusual. We define ξ n using the training data Õn t in the tube n:

ξ n = ρ × min t p( Õn t |M n ) , (8)
where ρ is a constant term accounting for noise in the training data.

Experimental Results 1

We evaluate the effectiveness of our approach on three data sets: one simulated crowded scene and two real-world extremely crowded scenes. We train a set of the distribution-based HMMs on a sequence of the usual state of the scene and use them to detect unusual activities in query videos of the same scene.

The ground truth was hand-labeled for all data sets to quantitatively evaluate The synthetic crowded scene was generated by translating a texture of a crowd across the frame, resulting in large motion variations and nonuniform motion along border areas. The image sequence consists of 216 tubes and 9, 072 total cuboid observations. Several smaller images were inserted moving in arbitrary directions to simulate unusual motion activities. The thresholds used in this experiment were d KL = 0.02, d Σ = 5, d µ = 1, and d K = 400. The Receiver Operating Characteristic (ROC) curve for this example is shown in Fig. 5, and is produced by varying values of the weighting scalar ρ in Eq. 8. Our results achieve a false positive rate of 0.009 and a true positive rate of 1.0 using a weighted scalar of 0.005. The false detections occurred in cuboids of no motion and texture. Though Eq. 3 reduces these sensitivities, the synthetic nature of the data set results in small, numerically stable distributions, increasing the KL distance enough to cause a false positive.

Videos of two extremely crowded real-world scenes were also used to evaluate the performance. For both data sets, thresholds in the KL distance were set to d Σ = 1, d µ = 1, and d K = 1000. The first, illustrated on the left in Fig. 3, is a video sequence from an extremely crowded concourse of a railway station. The scene contains a large number of moving and loitering pedestrians and employees directing traffic flow. The query video contains station employees walking against the flow of traffic and irregular pedestrian motions. The training video contains 9, 664 cuboids and the query video 1, 216. The threshold d KL is .06. The second real-world data set, shown on the right in Fig. 3, is a wide-angle view of pedestrian traffic at a railway terminal. The motion of the crowd occurs in a more constant direction than the first real-world data set, however still contains excessive occlusions and motion variations. As illustrated in Fig. 5, our approach achieves a false positive rate of 0.15 and a true positive rate of 0.92 with a weighting scalar of 10 -91 for the first data set, and a false positive rate of 0.13 and a true positive rate of 0.97 at a weighting scalar of 10 -42 for the second. A visualization of the detection results for this data set is shown in Fig. 4. Employees crossing the scene against the pedestrian traffic flow activity in the concourse, and pedestrians loitering and reversing direction in the ticket gates are successfully detected as unusual. The weight scalar values represent how much variability occurs in the motion patterns. The larger value in the second experiment indicates the usual motion patterns are more defined, and directly relates to the motion sensitivity a human operator would likely observe. Intuitively, unusual behavior beyond what is detected here, such as that warranting personnel intervention, would be satisfied with an even larger weighting scalar.

False positives occur in both experiments for slightly irregular motion patterns, such as after pedestrians exit the gate, and areas of little motion, such as where the floor of the station is visible. These motion pattern variations have similar severity to those detected as unusual. The few false negatives in both real-world examples occur adjacent to true positives, which suggests they are harmless in practical scenarios. We expect these can be avoided by accounting for the statistical information in surrounding local areas, which we plan to pursue as future work.

The effects of increasing the training data size for the Ticket Gate dataset are shown in Fig. 5. As expected, the performance increases with the training data size, and approaches a steady state with more than 100 observations per tube. The performance with only 10 observations per tube achieves a false positive rate of 0.22 and true positive rate of 0.84. This is largely due to the window around d KL for σ s in Eq. 6 when there are insufficient observations for specific prototypes, and the inclusion of disjoint motion patterns in the prototype construction. The performance with such small training data reflects the robust motion pattern representation captured by the distribution-based HMMs.

Conclusion

In this paper we introduced a novel statistical framework for analyzing local spatio-temporal motion patterns in extremely crowded scenes. Motion patterns are represented with multivariate Gaussian distributions, and prototypical occurrences of these motion patterns are identified, canonically representing the motion variations in the video sequence. The temporal statistical variation of the motion patterns is modeled in a robust, statistical framework using a novel distribution-based Hidden Markov Model.

Our results indicate that local spatio-temporal motion patterns are a suitable representation for analyzing extremely crowded scenes. Their use is demonstrated on real-world data of extremely crowded scenes, and successfully detects unusual motion patterns in pedestrian behavior including movement against the normal flow of traffic, loitering, and traffic congestion. We believe the proposed framework can play an important role in video analysis of extremely crowded scenes. We are currently investigating methods for incorporating local spatial statistics and believe this will lead to a more vivid description of the local activity and improved detection accuracy.

Fig. 1 .

 1 Fig. 1. Two frames from an extremely crowded scene that pose significant problems including appearance variations (a), frequent occlusions (b), and concurrent, independent activities (c) and (d). We derive a novel computational framework that models the temporal statistical behavior of local spatio-temporal motion patterns to analyze such videos.

Fig. 2 .

 2 Fig. 2. A schematic overview of the framework. (a) The video sequence is divided into local spatio-temporal volumes (cuboids). (b) The motion pattern is represented by a 3D Gaussian of spatio-temporal gradients. (c) Prototypical motion patterns are identified by grouping similar motion patterns that may lie at disjoint space-time locations. (d) Prototypes model the motion pattern variation in the video with a 1D normal distribution of 3D Gaussians, i.e. a distribution of distributions. (e) A distributionbased HMM is trained for each tube using the prototypical motion patterns for hidden states and 3D Gaussians as observations.

Fig. 3 .

 3 Fig. 3. Two extremely crowded real-world scenes include a railway station concourse (left) and ticket gate (right). The top half of the original frames are excluded from modeling, as they only contain views of the station ceiling.

Fig. 4 .

 4 Fig. 4. Detection of unusual events in the concourse video (left) and the ticket gate (right). Correctly classified unusual cuboids are highlighted in blue, usual cuboids in green, and false positives in magenta. The intensity of magenta blocks indicates the severity of false positives. Individuals reversing direction, loitering, and moving in irregular patterns are correctly classified as unusual. False positives indicate a sensitivity to low motion irregular patterns. A few false negatives are adjacent to true positives, thus we consider them harmless in practical scenarios. the performance, and all threshold values were selected empirically. The size of cuboids is set to 40 × 40 × 20 for all experiments.

Fig. 5 .

 5 Fig. 5. ROC curves for the synthetic and real-world extremely crowded scenes (a). Effects of increased training data on the Ticket Gate dataset (b). instances of people reversing direction and pausing in traffic. The training video contains 8, 288 cuboids and the query video 840. The threshold d KL is 0.05.As illustrated in Fig.5, our approach achieves a false positive rate of 0.15 and a true positive rate of 0.92 with a weighting scalar of 10 -91 for the first data set, and a false positive rate of 0.13 and a true positive rate of 0.97 at a weighting scalar of 10 -42 for the second. A visualization of the detection results for this data set is shown in Fig.4. Employees crossing the scene against the pedestrian traffic flow activity in the concourse, and pedestrians loitering and reversing direction in the ticket gates are successfully detected as unusual. The weight scalar values represent how much variability occurs in the motion patterns. The larger value in the second experiment indicates the usual motion patterns are more defined, and directly relates to the motion sensitivity a human operator would likely observe. Intuitively, unusual behavior beyond what is detected here, such as that warranting personnel intervention, would be satisfied with an even larger weighting scalar.False positives occur in both experiments for slightly irregular motion patterns, such as after pedestrians exit the gate, and areas of little motion, such as where the floor of the station is visible. These motion pattern variations have similar severity to those detected as unusual. The few false negatives in both real-world examples occur adjacent to true positives, which suggests they are harmless in practical scenarios. We expect these can be avoided by accounting for the statistical information in surrounding local areas, which we plan to pursue as future work.The effects of increasing the training data size for the Ticket Gate dataset are shown in Fig.5. As expected, the performance increases with the training data size, and approaches a steady state with more than 100 observations per tube. The performance with only 10 observations per tube achieves a false positive rate of 0.22 and true positive rate of 0.84. This is largely due to the window around d KL for σ s in Eq. 6 when there are insufficient observations for specific prototypes, and the inclusion of disjoint motion patterns in the prototype construction. The performance with such small training data reflects the robust motion pattern representation captured by the distribution-based HMMs.

A movie of results is located at http://www.cs.drexel.edu/ ~lak24/mlvma08.

Acknowledgments. This work was in part supported by Nippon Telegraph and Telephone Corporation and National Science Foundation under ITR award IIS-0426674.


Tony Tung
email: tung@vision.kuee.kyoto-u.ac.jp

Takashi Matsuyama

Human Motion Tracking using a Color-Based Particle Filter Driven by Optical Flow

In this paper, we present a new formulation for the problem of human motion tracking in video. Tracking is still a challenging problem when strong appearance changes occur as in videos of human in motion. Most trackers rely on a predefined template or on a training dataset to achieve detection and tracking. Therefore they are not efficient to track objects which appearance is not known in advance. A solution is to use an online method that updates iteratively a subspace of reference target models. In addition, we propose to integrate color and motion cues in a particle filter framework to track human body parts. The algorithm process consists in two modes, switching between detection and tracking. Detection steps involve trained classifiers to update estimated positions of the tracking windows, whereas tracking steps rely on an adaptative color-based particle filter coupled with optical flow estimations. The Earth Mover distance is used to compare color models in a global fashion, and constraints on flow features avoid drifting effects. The proposed method has revealed its efficiency to track body parts in motion and can cope with full appearance changes. Experiments were lead on challenging real world videos with poorly textured models and non-linear motions.

Introduction

Human motion tracking is a common requirement for many real world applications, such as video surveillance, games, cultural and medical applications (e.g. for motion and behavior study). The literature has provided successful algorithms to detect and track objects of a predefined class in image streams or videos. Simple object can be detected and tracked using various image features such as color regions, edges, contours, or texture. In the other hand, complex objects such as human faces require more sophisticated features to handle the multiple possible instances of the object class. For this purpose, statistical methods are a good alternative. First, a statistical model (or classifier) learns different patterns related to the object of interest (e.g. different views of human faces), including good and bad samples. And then the system is able to estimate whether a region contains an object of interest or not. This kind of approach has become very popular (e.g. the face detector of [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF] is well-known for its efficiency). The main drawbacks are that it requires prior knowledge on the object class which is usually a huge training dataset, and then it is somehow constrained to it. As a matter of fact, most of the tracking methods were not designed to keep the track of an object which appearance could strongly change. If there is no a priori knowledge on its multiple possible appearances, then the detection fails and the track is lost. Hence, tracking a head which turns completely, or tracking a hand in action remain challenging problems, as appearance changes occur quite frequently for human body parts in motion . Therefore we propose a new formulation dedicated to the problem of appearance changes for object tracking in video. Our approach integrates color cues and motion cues to establish a robust tracking. As well, an online iterative process updates a subspace of reference templates so that the tracking system remains robust to occlusions. The method workflow contains two modes, switching between detection and tracking. Detection steps involve trained classifiers to update estimated positions of the tracking windows. In particular, we use the cascade of boosted classifiers of Haar-like features by [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF] to perform head detection. Other body parts can be either detected using this technique with ad-hoc training samples, or chosen by users at the initialization step, or as well can be deduced based on prior knowledge on human shape features and constraints. The tracking steps rely on an adaptative color-based particle filter [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF] coupled with optical flow estimations [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF][START_REF] Tomasi | Detection and tracking of point features[END_REF]. The Earth Mover distance [START_REF] Rubner | A metric for distributions with applications to image databases[END_REF] has been chosen to compare color models due to its robustness to small color variations. Drift effects inherent to adaptative tracking methods are handled using optical flow estimations (motion features).

Our experiments show the accuracy and robustness of the proposed method on challenging video sequences of human in motion. For example, videos of yoga performances (stretching exercises at various speed) with poorly textured models and non-linear motions were used for testing (cf. Fig. 1). The rest of the paper is organized as follows. The next section discusses work related to the techniques presented in this paper. Section 3 presents an overview of the algorithm (initialization step and workflow). Section 4 describes the tracking process based on our color-based particle filter driven by optical flow. Section 5 presents experimental results. Section 6 concludes with a discussion on our contributions.

Related work

In the last decade, acquisition devices have become even more accurate and accessible for non-expert users. This has lead to a rapid growth of various imaging applications. In particular, the scientific community has shown a real interest to human body part detection and tracking. For example, face detection in images is nowadays a popular and well explored topic [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF][START_REF] Hjelmas | Face detection: a survey[END_REF][START_REF] Choudhury | Face detection and tracking in a video by propagating detection probabilities[END_REF]. In [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF], Viola and Jones proposed a cascade of boosted tree classifiers of Haar-like features. The classifier is first trained on positive and negative samples, and then the detection is performed by sliding a search window through candidate images and checking whether a region contains an object of interest or not. The technique is known to be fast and efficient, and can be tuned to detect any kind of object class if the classifier is trained on adapted samples.

Tracking in video is a popular field of research as well. Recognition from video is still challenging because frames are often of low quality, and details can be small (e.g. in video surveillance). Various approaches were proposed to track image features [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF][START_REF] Tomasi | Detection and tracking of point features[END_REF][START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Lucena | Evaluation of three optical flowbased observation models for tracking[END_REF][START_REF] Tola | A fast local descriptor for dense matching[END_REF]. Lucas, Tomasi and Kanade [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF][START_REF] Tomasi | Detection and tracking of point features[END_REF] first select the good features which are optimal for tracking, and then keep the tracks of these features in consecutive frames. The KLT feature tracker is often used for optical flow estimation to estimate the deformations between two frames. As a differential method, it assumes that the pixel intensity of objects is not significantly different between two frames.

Techniques based on prediction and correction as Kalman filter, and more recently particle filters have become widely used [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF][START_REF] Doucet | On sequential monte carlo sampling methods for bayesian filtering[END_REF][START_REF] Perez | Color-based probabilistic tracking[END_REF][START_REF] Sugimoto | Tracking human heads based on interaction between hypotheses with certainty[END_REF][START_REF] Okuma | A boosted particle filter: multitarget detection and tracking[END_REF][START_REF] Dorkania | Simultaneous facial action tracking and expression recognition using a particle filter[END_REF][START_REF] Wang | Online selecting discriminative tracking features using particle filter[END_REF][START_REF] Li | Tracking in low frame rate video: A cascade particle filter with discriminative observers of different lifespans[END_REF][START_REF] Ross | Incremental learning for robust visual tracking[END_REF][START_REF] Kim | Face tracking and recognition with visual constraints in real-world videos[END_REF]. Particle filters (or sequential Monte Carlo or Condensation) are Bayesian model estimation techniques based on simulation. The basic idea is to approximate a sequence of probability distributions using a large set of random samples (called particles). Then the particles are propagated through the frames based on importance sampling and resampling mechanisms. Usually, the particles converge rapidly to the distributions of interest. The algorithm allows robust tracking of objects in cluttered scene, and can handle non-linear motion models more complex than those commonly used in Kalman filters. The major differences between the different particle filter based approaches rely on the design of the sampling strategies, which make particles having higher probability mass in regions of interest.

In [START_REF] Black | Eigentracking: Robust matching and tracking of articulated objects using a view-based representation[END_REF][START_REF] Collins | On-line selection of discriminative tracking features[END_REF][START_REF] Wang | Online selecting discriminative tracking features using particle filter[END_REF][START_REF] Ross | Incremental learning for robust visual tracking[END_REF][START_REF] Kim | Face tracking and recognition with visual constraints in real-world videos[END_REF], linear dimension reduction methods (PCA, LDA) are used to extract feature vectors from the regions of interest. These approaches suit well for adaptative face tracking and can be formulated in the particle filtering framework as well [START_REF] Wang | Online selecting discriminative tracking features using particle filter[END_REF][START_REF] Ross | Incremental learning for robust visual tracking[END_REF][START_REF] Kim | Face tracking and recognition with visual constraints in real-world videos[END_REF]. Nevertheless they require a big training data set to be efficient [START_REF] Martinez | Pca versus lda[END_REF], and still cannot cope with unpredicted change of appearance. In the other hand, color-based models of regions can capture larger appearance variations [START_REF] Bradski | Computer vision face tracking as a component of a perceptual user interface[END_REF][START_REF] Comaniciu | Real-time tracking of non-rigid objects using mean shift[END_REF]. In [START_REF] Perez | Color-based probabilistic tracking[END_REF], the authors integrate a color-based model tracker (as in the Meanshift technique [START_REF] Comaniciu | Real-time tracking of non-rigid objects using mean shift[END_REF]) within a particle filter framework. The model uses color histograms in the HSV space and the Bhattacharyya distance for color distribution comparisons. Nevertheless these methods usually fail to track objects in motion or have an increasing drift on long video sequences due to strong appearance changes or important lighting variations [START_REF] Matthews | The template update problem[END_REF]. Indeed most algorithms assume that the model of the target object does not change significantly over time. To adapt the model to appearance changes and lighting variations, subspace of the target object features are extracted [START_REF] Collins | On-line selection of discriminative tracking features[END_REF][START_REF] Wang | Online selecting discriminative tracking features using particle filter[END_REF][START_REF] Ross | Incremental learning for robust visual tracking[END_REF][START_REF] Kim | Face tracking and recognition with visual constraints in real-world videos[END_REF]. In [START_REF] Ross | Incremental learning for robust visual tracking[END_REF], a subspace of eigenvectors representing the target object is incrementally updated through the tracking process. Thus, offline learning step is not required and tracking of unknown objects is possible. Recently, [START_REF] Kim | Face tracking and recognition with visual constraints in real-world videos[END_REF] proposed to extend this approach with additional terms in the data likelihood definition. In particular, the drift error is handled using an additional dataset of images. However, these approaches are particularly tuned for face tracking, and still require training datasets for every different view of faces.

The core of our approach divides into two steps which are detection and tracking, as [START_REF] Sugimoto | Tracking human heads based on interaction between hypotheses with certainty[END_REF][START_REF] Li | Tracking in low frame rate video: A cascade particle filter with discriminative observers of different lifespans[END_REF]. Switching between the two modes allows to dynamically update the search window to an accurate position whenever the detection is positive. In this paper, we propose to run a color-based particle filter to achieve the tracking process. Our tracker uses a subspace of color models of regions of interest extracted from the previous frames, and relies on them to estimate the position of the object in the current frame. The subspace is iteratively updated through the video sequence, and dynamically updated by the detection process. The detection is performed by a cascade of boosted classifiers [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF] and thus can be trained to detect any object class. We also introduce the Earth Mover distance to improve the robustness of tracking with lighting variations, and constraints based on optical flow estimations to cope with drift effects.

Algorithm overview

This section describes the algorithm workflow. The proposed approach combines two modes, switching between detection mode and tracking mode. The tracking process can be run independently if no detector is available for the class of the object of interest. Besides the tracking process, the detection improves the response accuracy online, and is used as well as initialization step. A subspace of color-based models is used to infer the object of interest location.

Initialization

The initialization step consists in defining the objects to track. In our framework, we focused on human body parts because of the wide rang of possible applications. Basically, there are three straightforward ways to define the regions of interest:

1. Automatic: this can be achieved by a detection process using statistical machine learning method (e.g. the face detector of [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF]). 2. Manual: regions of interest are defined by the user (e.g. by picking regions in the first frame). This allows to track any body part without having any prior knowledge. 3. Deduction: as the human body has self-constrained motions, its structure can be deduced using a priori knowledge and fuzzy rules. For example, a detected face gives some hints to deduce the torso position, etc.

In some of our experiments (cf. Sect. 5), we have combined the three approaches (e.g. head is automatically detected, torso is deduced, and hands are picked).

Afterwards, the regions of interest are used as reference templates on which the tracker relies on to process the next frames.

Workflow

Assuming the initialization occurs at time t 0 , then for every frame at t, t > t 0 , the tracker estimates the positions of M objects of interest {A i } i=1...M based on the color-model subspace S i t = {h i t-k , ..., h i t-1 }, where h i j denotes the colormodel of A i at time j, and k is the size of the subspaces (which in fact can be different for every object). Assuming a Bayesian framework (cf. Sect. 4), the hidden state x i t corresponding to the estimated position of A i at time t by the tracker, is inferred by S i t and x i t-1 . We denote by y i t the data corresponding to the detection of A i at time t, and z i t the response of the algorithm. Thus, if the detection of A i at t is positive, then z i t = y i t , else z i t = x i t . Indeed if the detection of A i at t is positive, then S i t+1 will be updated with the color model corresponding to y i t . And if not, then S i t+1 will be updated with the color model corresponding to x i t . The workflow is illustrated on Figure 2 with M = 1 and k = 1.

Particle filtering driven by optical flow

In this section we present our algorithm formulation based on color-based particle filtering [START_REF] Isard | Condensation -conditional density propagation for visual tracking[END_REF][START_REF] Perez | Color-based probabilistic tracking[END_REF] and optical flow estimations [START_REF] Tomasi | Detection and tracking of point features[END_REF]. We propose to use the Earth Mover Distance [START_REF] Rubner | A metric for distributions with applications to image databases[END_REF] to compare color models, and extracted motion features to improve tracking accuracy. Moreover our method updates iteratively a subspace of template models to handle appearance changes and partial occlusions.

Particle filtering

We denote by x t a target state at time t, z t the observation data at time t, and Z t = {z 1 , ..., z t } all the observations up to time t. Assuming a non-Gaussian state space model, the prior probability p(x t |Z t-1 ) at time t in a Markov process is defined as:

p(x t |Z t-1 ) = p(x t |x t-1 )p(x t-1 |Z t-1 )dx t-1 , (1)
where p(x t |x t-1 ) is a state transition distribution, and p(x t-1 |Z t-1 ) stands for a posterior probability at time t -1. The posterior probability which the tracking system aims to estimate at each time is defined as:

p(x t |Z t ) ∝ p(z t |x t )p(x t |Z t-1 ) , (2)
where p(z t |x t ) is the data likelihood at time t. According to the particle filtering framework, the posterior p(x t |Z t ) is approximated by a Dirac measure on a finite set of P particles {x i t } i=1...P following a sequential Monte Carlo framework [START_REF] Doucet | On sequential monte carlo sampling methods for bayesian filtering[END_REF]. Candidate particles are sampled by a proposal transition kernel q(x i t |x i t-1 , z t-1 ). The new filtering distribution is then approximated by a new sample set of particles {x i t } i=1...P having the importance weights {w i t } i=1...P , where

w i t ∝ p(z t |x i t )p(x i t |x i t-1 ) q(x i t |x i t-1 , z t-1 )
and

P i=1 w i t = 1 . (3)
The sample set {x i t } i=1...P can then be obtained by resampling {x i t } i=1...P with respect to {w i t } i=1...P . By default, the Bootstrap filter is chosen as proposal distribution: q(x i t |x i t-1 , z t-1 ) = p(x i t |x i t-1 ). Hence the weights can be computed by evaluating the corresponding data likelihood. Finally, x t is estimated upon the Monte Carlo approximation of the expectation xt = 1 P P i=1 x i t . We denote by E, the overall energy function:

E = E s + E m + E d ,
where E s is an energy related to color cues (cf. Sect. 4.2), E m and E d are energies related to motion features (cf. Sect. 4.4). E has lower values as the search window is close to the target object. Thus, to favor candidate regions which color distribution is similar to the reference model at time t, the data likelihood p(z t |x t ) is modeled as a Gaussian function:

p(z t |x i t ) ∝ exp - E σ 2 , ( 4
)
where σ is a scale factor, and therefore a small E returns a large weight.

Color-based model

The efficiency of color distributions to track color content of regions that match a reference color model has been demonstrated in [START_REF] Bradski | Computer vision face tracking as a component of a perceptual user interface[END_REF][START_REF] Comaniciu | Real-time tracking of non-rigid objects using mean shift[END_REF][START_REF] Perez | Color-based probabilistic tracking[END_REF]. They are represented by histograms to characterize the chromatic information of regions. Hence they are robust against non-rigidity and rotation. In addition, the Hue-Saturation-Value (HSV) color space has been chosen due to its low sensitivity to lighting condition. In our approach, color distributions are discretized into three histograms of N h , N s , and N v bins for the hue, saturation, and value respectively. Let α be h, s, or v, q t (x t ) = 1 3 α q α t (x t ), and q α t (x t ) = {q α t (i, x t )} i=1...Nα . q t (x t ) denotes the kernel density estimate of the color distribution in the candidate region R(x t ) of the state x t at time t, and is composed by:

q α t (i, x t ) = K α u∈R(xt) δ[h α (u) -i] , (5)
where K α is a normalization constant so that Nα i=1 q α t (i, x t ) = 1, h α is a function assigning the pixel color at location u to the corresponding histogram bin, and δ is the Kronecker delta function.

At time t, q t (x t ) is compared to a set of reference color model templates S t = {h t-k , ..., h t-1 }, where k is the number of templates. The templates are extracted iteratively from the detected regions at each frame. We recall that color model subspaces help to handle appearance changes and partial occlusions, and we define the energy function:

E s [S t , q t (x t )] = min h∈St (D 2 [h, q t (x t )]) , (6)
where D is a distance between color distributions (cf. Sect. 4.3).

Earth Mover distance

We propose to use the Earth Mover distance (EMD) [START_REF] Hillier | Introduction to mathematical programming[END_REF][START_REF] Rubner | A metric for distributions with applications to image databases[END_REF] to strengthen the property of invariance to lighting of the HSV color space. EMD allows to make global comparison of color distributions relying on a global optimization process. This method is more robust than approaches relying on histogram bin-to-bin distances that are more sensitive to quantization and small color changes. The distributions are represented by sets of weighted features called signatures. The EMD is then defined as the minimal amount of work needed to match a signature to another one. The notion of work relies on a metric (e.g. a distance) between two features. In our framework we use the L 1 norm as distance, and histogram bins as features.

Assuming two signatures to compare P = {(p 1 , w 1 ), ..., (p m , w m )} and Q = {(q 1 , u 1 ), ..., (q n , u n )}, P having m components p i with weight w i , and Q having n components q j with weight u j . The global optimization process consists in finding the amount of data f ij of a signature to be transported from the component i to the component j that minimizes the work W :

W = min fij ( m i=1 n j=1 d ij f ij ) , (7)
where d ij is the distance between the components p i and q j assuming the following constraints:

f ij ≥ 0 1 ≤ i ≤ m, 1 ≤ j ≤ n , n j=1 f ij ≤ w i 1 ≤ i ≤ m , m i=1 f ij ≤ u j 1 ≤ j ≤ n , m i=1 n j=1 f ij = min( m i=1 w i , n j=1 u j ) . (8)
The first constraint allows only the displacements from P to Q. The two following constraints bound the amount of data transported by P , and the amount of data received by Q to their respective weights. The last constraint sets the maximal amount of data that can be displaced.

The EMD distance D between two signatures P and Q is then defined as:

D (P, Q) = W N = m i=1 n j=1 d ij f ij m i=1 n j=1 f ij , (9)
where the normalization factor N ensures a good balance when comparing signatures of different size (N is the smallest sum of the signature weights). Note that EMD computation can be approximated in linear time with guaranteed error bounds [START_REF] Shirdhonkar | Approximate earth mover's distance in linear time[END_REF].

Motion cues

We propose to use motion features to guide the search window through the tracking process. Motion features are extracted using the KLT feature tracker [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF][START_REF] Tomasi | Detection and tracking of point features[END_REF]. The method detects feature windows and matches the similar ones between consecutive frames. Assuming the set Y t-1 = {y j t-1 } j=1...m of m motion features detected in the neighborhood region of the state x t-1 (cf. Sect. 4) at time t -1, and the set Y t = {y j t } j=1...m of matching features extracted at time t, then (Y t-1 , Y t ) = {(y j t-1 , y j t )} j=1...m forms a set of m motion vectors (optical flow field) between the frames at time t-1 and t. As well, we denote by Ỹi t the set of features detected in the neighborhood region of the particle xi t , and ỹt the position of the search window estimated by optical flow as: ỹt = x t-1 + median({y j t-1y j t } j=1...m ). Thus we define the following energy functions:

E m (x i t ) = α • xi t -ỹt 2 and E d = β • C( Ỹi t , Y t ) , (10)
where α and β are two constant values, and C is the following function:

C( Ỹi t , Y t ) = 1 - card( Ỹt ∩ Ỹi t ) card( Ỹt ) . ( 11
)
The data energy E m aims to favor the particles located around the object target position estimated by optical flow, whereas E d aims to prevent the drift effect. E d works as a constraint which attracts the particles near the estimated search window (cf. Fig. 3). E m and E d are introduced in the overall energy formulation as described in Sect. 4.2.

#1 #2 #3 # 4
Fig. 3. Using optical flow to improve tracking. The combination of color cues and motion cues allows to perform robust tracking and prevent drift effects. The tracking of hands is efficient even with a changing background.

Experimental results

Our algorithm has been tested on various real video sequences. For example, we have tracked the body parts of a lady practicing yoga (head, hands, torso, and feet) in different video sequences and from different viewpoints. The model wears simple clothes with no additional features (cf. Fig. 1 and Fig. 5). As well, we have tested the tracker on a model wearing traditional Japanese clothes which are more much complex and contain a lot of features (cf. Fig. 3). In this paper, the video frame sizes are 640x480 and 720x576 pixels and were acquired at 25 fps. The algorithm was run on a Core2Duo 3.0GHz with 4GB RAM. The following parameters were identical for all the experiments: we have used N h = 10, N s = 10 and N v = 10 for the quantization of color models, P = 200 particles, k = 5 for the color model subspace size, and σ 2 = 0.1 as scale factor of the likelihood model. The constant values α and β weight the contribution of the motion cues, and are tuned regarding to the frame size. He have defined a square window size of 40 pixels to determine the regions of interest. The proposed formulation has shown promising results. The Figures 1 and4 illustrate the robustness to appearance change, lighting variation and partial occlusion, thanks to the online update of the color-based model subspace combined with the Earth Mover distance and motion cues. For example, the system can track a head even if the face in no more visible (e.g. hidden by hair or due to changing viewpoint). Figure 3 illustrates an accurate tracking with free-drift effect of a hand with a varying background under the guidance of optical flow as motion cues. Figure 5 illustrates the robustness of our approach in comparison to a color-based particle filter (Condensation) [START_REF] Perez | Color-based probabilistic tracking[END_REF] that does not include our features. We show that the Condensation mixes regions having the same color shape and distribution whereas our tracker is not confused by the similar regions. This is due in particular to the addition of motion cues. The proposed approach integrates motion cues and a subspace of color models which is updated online through the video sequence. The system can track objects in motion with appearance change.

Conclusion

Human motion tracking in video is an attractive research field due to the numerous possible applications. The literature has provided powerful algorithms based on statistical methods especially dedicated to face detection and tracking. Nevertheless, it is still challenging to handle complex object classes such as human body parts which appearance changes occur quite frequently while in motion.

In this paper, we propose to integrate color cues and motion cues in a tracking process relying on a particle filter framework. We have used the Earth Mover distance to compare color-based model distribution in the HSV color space in order to strengthen the invariance to lighting condition. Combined with an online iterative update of color-based model subspace, we have obtained robustness to partial occlusion. We have also proposed to integrate extracted motion features (optical flow) to handle strong appearance changes and prevent drift effect. In addition, our tracking process is run jointly with a detection process that dynamically updates the system response. Our new formulation has been tested on real videos, and results on different sequences were shown. For future work, we believe our approach can be easily extended to handle a online manifold learning process. This would improve both detection and tracking modes.

Fig. 1 .

 1 Fig. 1. Body part tracking with color-based particle filter driven by optical flow. The proposed approach is robust to strong occlusion and full appearance change. Detected regions are denoted by red squares, and tracked regions by green squares.

Fig. 2 .

 2 Fig.2. Algorithm workflow. In this example, the detection state is positive at time t, and negative at t + 1. Hence, the algorithm response zt at time t is updated with y t , and zt+1 is updated with the tracker estimation xt+1 at time t + 1. St denotes the subspace of color models used to infer xt. As the detection is positive at t, St+1 takes into account the color model corresponding to y t .

Fig. 4 .

 4 Fig. 4. Tracking with appearance change. The proposed approach integrates motion cues and a subspace of color models which is updated online through the video sequence. The system can track objects in motion with appearance change.

  Particle filter driven by optical flow.

Fig. 5 .

 5 Fig. 5. Robust body part tracking. (a) Classical Condensation methods [2, 12] are confused by regions with similar color and shape content. (b) In frame #20, both hands are almost included in a same tracking window, but afterwards motion cues have helped to discriminate the different tracks.

Acknowledgments

The authors would like to thank Dr. Hiroaki Kawashima and Dr. Shohei Nobuhara for helpful discussions.