Fabio Martínez

Antoine Manzanera
email: antoine.manzanera@ensta-paristech.fr

Eduardo Romero
email: edromero@unal.edu.co

A spatio-temporal multi-scale motion descriptor from a spatially-constrained decomposition for online action recognition

This work presents a spatio-temporal motion descriptor that is computed from a spatiallyconstrained decomposition and applied to online classification and recognition of human activities. The method starts by computing a multi-scale dense optical flow that provides instantaneous velocity information for every pixel without explicit spatial regularization. Potential human actions are detected at each frame as spatially consistent moving regions and marked as Regions of Interest (RoIs). Each of these RoIs is then sequentially partitioned to obtain a spatial representation of small overlapped subregions with different sizes. Each of these region parts is characterized by a set of flow orientation histograms. A particular RoI is then described along the time by a set of recursively calculated statistics, that collect information from the temporal history of orientation histograms, to form the action descriptor. At any time, the whole descriptor can be extracted and labelled by a previously trained support vector machine. The method was evaluated using three different public datasets: (1) The VISOR dataset was used for two purposes: first, for global classification of short sequences containing individual actions, a task for which the method reached an average accuracy of 95% (sequence rate). Also, this dataset was used for recognition of multiple actions in long sequences, achieving an average per-frame accuracy of 92.3%. (2) the KTH dataset was used for global classification of activities and (3) the UT-datasets were used for evaluating the recognition task, obtaining an average accuracy of 80% (frame rate).

Introduction

Action recognition is a very active research domain with a large variety of potential applications: human computer interaction, biometric, health care assistance or surveillance, among others. This task, aimed to automatically segment and identify human activities in video sequences, is particularly difficult because of the high variations in geometry, scale and appearance. Such variations are namely present under not controlled illumination or occlusion conditions. Moreover, characterization of human dynamic introduces additional challenges, specifically: (1) activities can share similar gestures or motion primitives, for instance, leaving an object or get into a car, [START_REF] Vishwakarma | A survey on activity recognition and behavior understanding in video surveillance[END_REF] interactions with other humans or objects may occur, occluding the capture or producing very different dynamic patterns and (3) many of the proposed descriptors require a complete description of the activity along the video sequence to perform the recognition, this limitation could be critical in many real scenarios. Emerging recognition applications include the detection of actions in challenging scenarios, as well as detection of group activities, search for salient events within particular time intervals and object detection from a single view. These new tasks demand flexible descriptors that achieve an appropriate trade-off between accuracy and computation time for real applications. For instance, some new applications require to capture local and salient regions with their associated semantics. Many other tasks require a competitive detection of salient regions but using efficient and soft descriptors that allow decision in real time. Comprehensive surveys of the different proposed approaches and applications can be found in [START_REF] Aggarwal | Human activity analysis: A review[END_REF][START_REF] Vishwakarma | A survey on activity recognition and behavior understanding in video surveillance[END_REF][START_REF] Borges | Video-based human behavior understanding: A survey[END_REF][START_REF] Vrigkas | A review of human activity recognition methods[END_REF] Under certain controlled conditions, the actions can be represented as a continuous progression of the body geometry, whereby temporal variations of the human shape are associated with specific activities [START_REF] Liu | Single/multi-view human action recognition via regularized multi-task learning[END_REF]. These approaches are however limited in outdoors or open scenarios where no illumination control is possible. The motion captured in such conditions is in general contaminated since the dynamic quantification depends on a proper computation of silhouettes. Furthermore, these approaches may fail by the under-segmentation or occlusion problems [START_REF] Vrigkas | A review of human activity recognition methods[END_REF].

Additional methods for action recognition are based on the computation of local features along the video sequence, that in general, overcome problems relative to the occlusion and some geometrical variations. Once the spatio-temporal features are computed, several statistics are applied to code the action description, for instance by computing bag-of-features to analyse the occurrence of patches [START_REF] Cao | Action recognition using 3D DAISY descriptor[END_REF][START_REF] Samanta | Space-time facet model for human activity classification[END_REF], or by using rule based methods, where the activity detection is represented as a maximum-weight connected sub-graph [START_REF] Chen | Efficient activity detection with max-subgraph search[END_REF]. These local features are however dependent on the object appearance, the recording conditions and a large number of patches. In such approaches, the set of patches used to represent the sequence of video ignore temporal correlations. However, some approaches do compute space-time information from particular motion patterns, aiming to follow the objects in motion along the sequence [START_REF] Wang | A robust and efficient video representation for action recognition[END_REF]. These approaches characterize the spacetime information by computing features such as HOF (Histograms of Optical Flow), MBH (Motion Boundary Histograms) and HOG (Histograms of Oriented Gradients), which together represent the activities under a bag-of-feature framework. In this case, the features computed form a dictionary which is used to compute the signature of the video. These space-time features nevertheless are computed for fixed intervals of time, a condition too restrictive for on-line applications containing a wide variety of actions. Moreover, variability can even be larger if one considers computed features mainly dependent on their particular appearance under variable illumination conditions in open scenarios where typically activities are developed.

Motion description from dense or sparse optical flow primitives, has been also widely used to characterize and recognize individual and interactive activities. Such descriptors have been popular since they are relatively independent of the visual appearance and allow to capture complex patterns of human actions. For instance, in [START_REF] Chaudhry | Histograms of oriented optical flow and binet-cauchy kernels on nonlinear dynamical systems for the recognition of human actions[END_REF] human gestures were recognized by applying histograms of oriented optical Flow (HOOF), made invariant to vertical symmetry. This approach however misses local details that might define a particular activity, for instance the motion relationship between the limbs. Likewise, Riemenschneider et. al [START_REF] Riemenschneider | Bag of Optical Flow Volumes for Image Sequence Recognition[END_REF] compute different dynamic relationships from an optical flow combined with a bag-of-features model that aims to determine the occurrence of motion patterns. These methods in general highlight the most frequent dynamic patterns but lose temporal and spatial probabilistic feature distributions. Also, block-based histograms of optical flow have been proposed to partially preserve the spatial distribution of motion patterns, which in turn can be combined with local contour orientations [START_REF] Ikizler | Human action recognition with line and flow histograms[END_REF]. This method can distinguish simple periodic actions, but the motion characterization may be dependent on the spatial grid configuration. Other approaches like [START_REF] Tabia | Motion histogram quantification for human action recognition[END_REF] and [START_REF] Zhang | Motion context: A new representation for human action recognition[END_REF] use polar space representations to code regionally the optical flow and to characterize activities. Besides, in the work proposed by Michalis et. al [START_REF] Vrigkas | Matching mixtures of curves for human action recognition[END_REF] a set of time series features are computed from the optical flow to represent the activ-ities. These series are clustered using Gaussian mixture modeling (GMM) and then a canonical time warping allows the comparison between the training and the test samples. A main limitation of these methods is that they compute their descriptors on entire sequences, thus do not explicitly provide on-line recognition capabilities. Likewise, the local features coded in their descriptors are in most cases appearance dependent.

Currently, machine learning approaches based on convolutional deep models have been applied to construct features used in action classification, achieving high accuracy from large training sets [START_REF] Ji | 3D convolutional neural networks for human action recognition[END_REF], [START_REF] Taylor | Convolutional learning of spatio-temporal features[END_REF], [START_REF] Baccouche | Sequential deep learning for human action recognition[END_REF]. Nevertheless, these methods are computationally expensive and present an intrinsic time-delay that together constitute a critical limitation in real action recognition applications. Additionally, these methods are dependent on a bias parameter that has to be learned along with the spatio-temporal kernel weight parameters, a task for which the whole video sequence is required. For instance, in [START_REF] Ryoo | Pooled motion features for first-person videos[END_REF], different temporal scales were proposed to recognize activities in single perspective videos, as input to a CNN architecture. Such work reports high recognition rates but at a high computational cost because of the resultant high dimensional descriptors that must be learned from video sequences.

The main contribution of this work is a spatio-temporal multi-scale descriptor composed of a set of recursive statistics that collect the RoI temporal information in orientation histograms. Each of these RoIs is spatially divided into several overlapping sub-regions with different sizes and each of these subregions is in turn temporally characterized by computing a flow orientation histogram, weighted by the norm of the velocity. A complete dynamic description is then achieved by recursively computing statistics of the histograms spanning different temporal intervals. Such descriptor is capable of determining locations of human actions with potential interest. The resultant descriptor is used as input to a trained SVM classifier. Evaluation is performed using two video-surveillance based human action recognition datasets, made of real actions recorded with static (or quasi static) cameras. The performance of the proposed approach proved to be competitive with respect to the state-of-the-art. This paper is organized as follows: Section 2 introduces the proposed method, section 3 presents results and the evaluation of the method, and finally section 4 presents a discussion and concludes with possible future works.

The Proposed Approach

Visual systems are naturally entailed with the ability of optimally detecting, recognizing and interpreting visual information, in many cluttered scenarios, using practically the same evolved mechanism [START_REF] Ostrovsky | Visual parsing after recovery from blindness[END_REF]. In general, the visual system explores an overfragmented environment and constructs a valid world representation by recognizing a relevant motion when there exists a sort of temporal coherence during a time interval. Hence, a major challenge at analysing any human action is then the optimal duration, during which such analysis should be carried out. This interval is obviously dependent on the action complexity, for instance a walking action may be characterized during very short periods while composed actions, such as getting into a car, may require longer times. This work introduces a novel strategy that integrates several temporal scales of an overlapped representation of a Region of Interest, which in due turn is determined from the optical flow field. The method starts by computing a dense optical flow, using a local jet feature approach, from which a spatial coherence during a certain time helps to discover potential RoIs. Each RoI is then divided to obtain an overlapped representation that allows to integrate local and global dynamic information. Any of these subregions is basically characterized by a set of statistics, computed from the history of the orientation histograms, a complex dynamic structure that, at each time, stores the information flow between consecutive frames.

Dense optical flow estimation using local jet features

The computation of an apparent velocity flow field has been successfully applied to recover motion patterns from object orientation [START_REF] Vishwakarma | A survey on activity recognition and behavior understanding in video surveillance[END_REF], [START_REF] Borges | Video-based human behavior understanding: A survey[END_REF]. The herein proposed strategy characterizes the motion by computing a velocity flow field that is used, first, to localise potential actions in the scene, and second to describe such actions using space × time statistics of velocities. Any dense or semidense optical flow algorithm may be used for such task. In this work we used the nearest neighbour search in the local jet feature space (see [START_REF] Manzanera | Local jet feature space framework for image processing and representation[END_REF] for more details). It consists in projecting every pixel to the feature space made of the spatial derivatives of different orders, computed at several scales (the local jet). For each frame t and every pixel x, the apparent velocity vector V t (x) is estimated by searching the most similar feature in the local jet space at the frame t -1. In the literature, most dense optical flow algorithms obtain smooth dense velocity fields by introducing different orders of spatial restrictions that limit global motion computations. In contrast, the method herein used provides a dense optical flow field without explicit spatial regularization and an implicit multi-scale estimation by using regional spatial characteristics. In this sense, the proposes approach provides a better motion estimation at a global level. In our experiments, we used 5 scales, with σ n+1 = 2σ n , and three first order derivatives, resulting in a pixel-level descriptor vector of dimension 15 (Figure 1, first column).

Localisation of potential actions and overlapped RoIs representation

The second step consists in localising the potential actions by extracting rectangular Regions of Interest (RoIs) containing a set of the closest pixels with significant motion. The pixels whose velocity norm is above a certain threshold τ s are spatially aggregated using a morphological closing with a disk of radius R c . Then, multiple moving sub-regions can pop out the scene {a i } n i=0 . In a particular frame, the regions of connected components with area smaller than A m are discarded, and the rest are grouped if their distance D m is less than τ t . Otherwise, they will be considered independent regions of interest that will be processed as independent actions. For consecutive frames, such spatial regions are also indexed as the same region if the distance D m is less than the threshold τ t . Such temporal association of the RoI is fundamental for computing the time statistics (see Sec. 2.4). The distance D m = a i -a j is simply defined as an Euclidean metric between the centroid coordinates of any two connected components a i , a j , in both spatial and temporal axes.

(see Sec.2.4)
In video sequences with multiple targets, multiple regions of interest are identified if the distance between these regions is larger than the pre-established distance threshold τ t . If there are different actors in the scene and the between-object distance D m is small, then pair-wise actions are grouped and the complete motion is considered as human interaction. For a typical sequence of human interaction, initially independent actions can be considered because of the established distance threshold τ t , but with the time such RoIs can be grouped as a unique interaction. For each detected RoI, an independent motion descriptor is computed and then mapped to the support vector machine as described hereafter. The threshold for grouping the spatiotemporal RoIs was set to τ t = 0.1 • (2 • (W + H)) , while the grouping of subregions was set to t s = 0.1A m . Here W and H correspond to frame width and height, while A m corresponds to the area of region m.

Afterwards, each of the selected RoIs is partitioned as illustrated in Figure 1, obtaining a set of overlapped subregions with different sizes. The total number of subregions for n layers (splits) is:

L n = 2 + n L=2 L 2
, where the first layer L 1 vertically splits the RoI into two parts, and then each layer is proportionally split into the same number of divisions for the two axes. For instance, the total number of subregions using four layers (L 4 ) is 31. This spatial RoI representation allows us to represent the RoI as a set of different layers which at each time captures finer regions, and therefore more localized dynamic patterns. Perceptually inspired [START_REF] Van Hateren | Independent component analysis of natural image sequences yields spatio-temporal filters similar to simple cells in p0rimary visual cortex[END_REF], such representation captures global and local appearance motion patterns, i.e., high statistical dependence of these subregions. Thus, the salient dynamic emerges at the different scales, making the computed statistics store the dependency of the different patterns at the several scales and times. Thus, the spatially located salient dynamics is highlighted by the different scales, which produce a redundant representation of the motion patterns. In the proposed approach there are not explicit metrics to capture the correlation among the regions captured at different layers. However, since the RoI is represented using different layers, the regions with motion will be predominant in the distribution of the motion descriptor.

Histogram of Velocity Orientations

For each of these RoI subregions, a per-frame temporal descriptor is built up using the distribution of the instantaneous motion orientations. For a non-null flow vector V let Ω(V) be its orientation, quantised to N bins. As in the Histogram of Oriented Gradients, HOG [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], a per-frame motion orientation histogram is computed as the occurrence of flow vectors with similar orientations, weighted by their norms. A dominant direction may then be the result of many vectors or few vectors with large norms; such histogram reads as:

H t (φ) = {x∈RoI;Vt(x) =0;Ω(Vt(x))=φ} V t (x) {x∈RoI} V t (x)
where φ ∈ {φ 0 . . . φ N -1 }, N being the number of orientations, herein set to 64 (see Figure 2, first row).

Multi-scale motion descriptor

Visual systems are in general capable of recognizing activities by somehow integrating simple primitives during different intervals of time [START_REF] Ostrovsky | Visual parsing after recovery from blindness[END_REF]. It is well known that most of the retina cells respond to transients and basic information of edges. Overall, this information is organized in terms of space and time by cells that are topographically connected to the visual field and that are triggered by variable time stimuli. This characterization allows, among others, to filter specific noise out, to analyse complex dynamics and to recognize objects during variable intervals of information. In action recognition applications, human activities may be thought of as the succession of atomic motions / gestures that can be described by simpler dynamics. Actions involving periodic motions like "walking" or "boxing" can be described efficiently since all their atomic gestures can be characterized during limited temporal intervals. Activities like "get into a car" or "leave an object" are more complex and typically involve several periodic and aperiodic parts. In such a case, the computation of global features over the flow trajectory may result insufficient and, in many times, with an important loss of relevant information, as for instance the transition between simple actions. Hence, a successful temporal descriptor should combine the analysis spanning different temporal windows.

The new descriptor herein introduced is designed to combine information from different time periods. For doing so, a set of relevant motion features are computed during variable time intervals (temporal scales) using recursive estimations as the cumulated statistics from the orientation histograms. Firstly, the temporal mean and variance are estimated using the recursive exponential filters, where H t (φ j ) is the j th histogram bin, computed at time t and α ∈ [0, 1] is a decay parameter relative to the time depth. For each histogram bin, two additional statistics are recursively estimated: the temporal maximum and minimum, using forgetting morphological operators [START_REF] Richefeu | A new hybrid differential filter for motion detection[END_REF]. The computation of the recursive statistics is illustrated in Algorithm 1.

The computed non-linear features complement the dynamic information estimated by the mean and standard deviation. The proposed descriptor combines a set of features recursively computed to cope with different complex and periodic human activities. Furthermore, the motion descriptor shows interesting properties: (1) little sensitivity to the impulse noise because of the forgetting term, corresponding to the exponentially decreasing weights attached to the past values; (2) periodic and composed motions are characterized by a set of global features computed at several time Fig. 2. Computation of the multiscale motion description from a spatially-constrained decomposed RoI. In (a) the candidate action bounded in a RoI is sequentially partitioned and for each subregion a motion orientation histogram is computed. In (b), several temporal recursive statistics are illustrated, they are computed per bin, using different α parameters that achieve variable time intervals for the analysis. This figure illustrates the principles of the different steps but does not necessarily display the features corresponding to the real data. Finally, in (c) each multiscalemotion descriptor is mapped over a previously trained support vector machine to predict the action.

scales, including both recent and old dynamic information; (3) the recursive computation achieves an efficient use of the memory. Provided that some activities are commonly composed of different simpler actions, the statistics and the multiscale estimation facilitate discrimination of periodic and aperiodic motions.

Frame activity recognition

Recursively computed statistics estimate different characteristics for several time scales. This particular attribute of the proposed descriptor is a powerful tool for representing actions of interest in incomplete videos or streaming sequences. In practice, at each frame, the motion descriptor is Algorithm 1 Recursive computation of statistics that temporally integrate the motion histograms computed at each sub-region.

Initialization:

for each bin φ j of the orientation do

µ 0 (φ j ) = m 0 (φ j ) = M 0 (φ j ) = H 0 (φ j ) v 0 (φ j ) =
µ t (φ j ) = µ t-1 (φ j ) + α(H t (φ j ) -µ t-1 (φ j )) 2. Recursive variance: v t (φ j ) = v t-1 (φ j ) + α ((H t (φ j ) -µ t (φ j )) 2 -v t-1 (φ j )) 3. Forgetting Max: M t (φ j ) = αH t (φ j ) + (1 -α) max(H t (φ j ), M t-1 (φ j )) 4. Forgetting Min: m t (φ j ) = αH t (φ j ) + (1 -α) min(H t (φ j ), m t-1 (φ j
)) end for end for end for composed of the set of scalar statistics computed at different time scales and regions as

SR d = {µ α i , σ α i , M α i , m α i } n
i=0 . These statistics are constantly updated, storing information from all the time scales considered, using the α i parameters. The vector of updated statistics feeds a previously trained support vector machine and a corresponding activity label is returned for the particular region of interest. This methodology is illustrated in Figure 3.

For training purposes, several samples of incomplete videos were obtained from the original training set. For doing so, each of the videos was split several times, setting the video length to the alpha parameters considered in the experiments. This set was used to train the SVM that returns a label action for each time.

SVM Classification and Recognition

Finally, for each potential action, a descriptor of dimension d is produced, such that:

d = N div × N φ × N stat × N α
with N div the total number of subregions of the overlapped representation, N φ the number of orientations for the velocity, N stat the number of time statistics computed for each bin, and N α the number of time scales.

The recognition of each potential activity is carried out by a Support Vector Machine (SVM) classifier since this constitutes a proper balance between accuracy and low computational cost. SVMs have been successfully applied to many pattern recognition problems, given their robustness, generalization aptness and low computational cost. Particularly, for action recognition, several approaches have been reported to use SVM classifiers [START_REF] Aggarwal | Human activity analysis: A review[END_REF], [START_REF] Schuldt | Recognizing human actions: A local SVM approach[END_REF], [START_REF] Dollár | Behavior recognition via sparse spatiotemporal features[END_REF]. The present approach was implemented using a One against one SVM multiclass classification with a Radial Basis Function (RBF) kernel [START_REF] Chang | LIBSVM: a library for support vector machines[END_REF]. Here, the classes represent the actions and optimal hyperplanes separate them by a classical max-margin formulation. For k motion classes, a majority voting strategy is applied on the outputs of the k(k-1) 2 binary classifiers. A (γ, C)-parameter sensitivity analysis was performed with a grid-search using a cross-validation scheme and selecting the parameters with the largest number of true positives.

Evaluation and Results

Experimentation was carried out with three public datasets, commonly used for assessing human action recognition tasks: (1) the ViSOR dataset (Video Surveillance Online Repository), captured by a real world surveillance system [START_REF] Vezzani | Video surveillance online repository (visor): an integrated framework[END_REF][START_REF] Ballan | Effective codebooks for human action categorization[END_REF], (2) UT-Interaction dataset (High-level Human Interaction Recognition Challenge) which is dedicated to complex human activities in real world scenarios [START_REF] Ryoo | UT-Interaction Dataset[END_REF], and (3) the classical KTH dataset which contains several activities recorded from different viewpoints [START_REF] Schuldt | Recognizing human actions: A local SVM approach[END_REF]. The ViSOR dataset is composed of videos showing 5 different human activities: walking, running, getting into a car, leaving an object and people shaking hands. These videos were captured by a stationary camera and contain a different number of actors and activities, (examples of actions are shown in Figure 4, first row).

The challenge is related with recognizing individual activities performed by several actors with different appearance, when the scene background differs and the motion direction may vary during the video sequence. Experiments with the ViSOR dataset consisted in classifying the different actions in 150 videos with individual human activities. For testing, the dataset was partitioned into two complementary subsets, performing the analysis on the training set (60 %), and validating such analysis on the testing set (40 %). Each round of the validation scheme we applied randomly selects those two subsets of the original ViSOR set. A total of four rounds were performed, and the reported accuracy was the average over the rounds.

The best reported performance was herein obtained by quantifying the motion into 32 bins. The actions in ViSOR sequences have a relative periodic pattern and the dynamic description can be more easily recovered, therefore a 32 bins histogram allowed to capture these motions. In consequence, this reduced resolution allows us to built a compact descriptor that can be operated in online applications. Every RoI was built using three layers: then it was split into 2, 4, and then 9 divisions, representing a total of 15 histogram supports.

The multi-temporal motion descriptor was computed using different decay parameters α i = 2 -i , with i ∈ {4, 5, 6} for 3 scales (i.e. time depths varying between 16 and 64 frames) and i ∈ {5, 6, 7, 8, 9} for 5 scales (i.e. time depths varying between 32 and 512 frames). In this dataset, 3 scales obtained good results for the classification task, basically because most activities span a time period between 16 and 64 frames. The herein proposed strategy has succeeded in recognizing complex human actions in real scenarios. Such spatio-temporal descriptor has been able of popping out the most salient regions in terms of dynamic information by tracking the statistical dependency among the different partitions of the potential RoIs. This strategy was crucial when discriminating composed actions such as getting into a car or leave an object, since the decomposition into motion primitives captured the differences between similar actions. Table 1 Confusion Matrix obtained with the ViSOR dataset, using the proposed motion descriptor with 3 temporal scales. Results are in %. In average, the proposed approach achieves an accuracy of 93.3% . Some misclassified actions are walking and running Table 1 and 2 show the confusion matrices obtained with the ViSOR dataset using a motion descriptor parametrized with 3 and 5 temporal scales, respectively. In general, these results demonstrate a good performance of the proposed descriptor in real-surveillance applications, obtaining an average accuracy of 93.3 and 96.7. As expected, the motion descriptor may confuse actions like "walking" and "running", basically because their representation in terms of dynamic primitives is similar. Particularly, the activity labeled as "get into a car" is composed of a first part with a classical walking pattern which is followed by a bending down action to open the car. The proposed descriptor fails because most of the activity is devoted to the "walking" action. These failures were reported in Table 2. Table 2 Confusion Matrix obtained with the ViSOR dataset using the proposed motion descriptor with 5 temporal scales. Results are in %. In average the proposed approach achieved an accuracy of 96.67%

Thanks to the recursive nature of the descriptor, action prediction can be made at any time of the sequence, which makes this approach adapted to online detection. For doing so, the motion is computed at each frame and mapped to a previously trained SVM model. We evaluated the accuracy of our approach in an online action recognition task for 5 long videos (each ∼ 400 frames long) of the ViSOR dataset. In this evaluation, the online prediction performed by the herein proposed approach achieved an average per-frame accuracy of 92.3%.

Figure 5 illustrates the performance of the proposed method at the frame level for different ViSOR video sequences. The proposed approach generally achieves good recognition rates after few frames thanks to the recursive nature of the descriptor and its multiple time scales. When an action starts, the motion descriptor oscillates among different activities with close dynamics, until the history of the action reaches a sufficient number of frames. Specifically, a prediction delay is observed between frames 200 and 220 since the online descriptor, previously stabilized to the "walking" action, requires to recursively "forget" this motion pattern. On the left of the figure, the motion descriptor oscillates in the first frames by the similarity between "walking" and "get into a car" during the first part of the action. Some fluctuations are also observed in the middle of the sequence since actors remain sometimes static and therefore the optical flow is insufficient to properly update the descriptor.

Additionally, the proposed motion descriptor was evaluated in the classical KTH dataset. This dataset contains six human action classes: walking, jogging, running, boxing, waving and clapping. Each action is performed by 25 subjects in four different scenarios with different scales, clothes and scene variations. This dataset contains a total of 2 391 video sequences. The proposed approach was evaluated following the original experimental setup described in [START_REF] Schuldt | Recognizing human actions: A local SVM approach[END_REF]. Since KTH contains individual actions recorded over relatively static scenarios, the same parameter configuration as ViSOR was applied. Every RoI was built using three layers as: {2, 4, 9}, representing a total of 15 histogram supports of 32 bins. In this dataset, the motion descriptor was computed using 3 temporal scales, using decay parameters 2 -i with i ∈ {4, 5, 6}. The proposed motion descriptor was also evaluated using four layers and five temporal scales but there were no significant improvements in the classification task.

Table 3 shows the confusion matrix obtained for the KTH dataset using the proposed motion descriptor for the complete video sequence.The action label of each video was assigned by selecting the label most frequently predicted after computing the motion descriptor at each frame. The motion descriptor, as expected, confuses in some cases "jogging" and "running" activities, because of the similarities of such actions. The "clapping" action also generates misclassification because the periodic motion of limbs can be confused with other periodic actions. However these results show robustness with respect to the viewpoint, that can be further enhanced in future extensions of the proposed action descriptor.

The proposed spatio-temporal motion descriptor was also evaluated using the UT-interaction dataset. This dataset contains six different human interactions: shake-hands, point, hug, push, kick and punch (example of these actions are illustrated in Figure 4, second row) [START_REF] Ryoo | UT-Interaction Dataset[END_REF]. The actions included in this dataset are much more complex, i.e., they contain more interactions between different people, with a higher variability in the human appearance and motion patterns. A total of 120 videos of this dataset were used for assessment. Each video has a spatial resolution of 720 × 480 and a frame rate of 30 f ps. A ten-fold leave-one-out cross-validation was performed, as described in [START_REF] Ryoo | UT-Interaction Dataset[END_REF].

Given the complexity of interactions and the similar dynamic relationships among the different box hc hw jog run walk box 91 4.8 0.0 0.0 0.0 4.2 hc 0.0 89 0.0 0.0 11 0.0 hw 3.0 5.0 92 0.0 0.0 0.0 jogg 0.0 0.0 0.0 89 4.0 7.0 run 0.0 0.0 0.0 12 88 0.0 walk 0.0 0.0 10 0.0 0.0 90

Table 3 Confusion Matrix obtained with the KTH dataset.Results are in %. The proposed approach achieves an average score close to 90% for the multi-class recognition recorded activities, the motion directions were quantized into 64 bins for each of the different RoI sub-regions. Such histogram resolution allows us to improve discrimination between actions like Punching and Pushing while maintaining a low computational cost.

A denser histogram representation was set for this dataset because of the dynamic complexity of the composed activities. Two different subregion RoI configurations were herein considered by using three (2, 4, 9) and four (2, 4, 9, 16) layers. The best configuration of the motion descriptor for the UT-interaction dataset was obtained when the RoI was split using four layers, corresponding to a total of 31 subregions. In average, for the two UT-interaction datasets, the average accuracy decreased 2% when the proposed motion descriptor was run using only 3 layers for the RoI representation. The proposed motion descriptor was also tested using two different configurations for the temporal scales as follows: {α i = 2 -i ; i ∈ {4.5, 6}} and {α i = 2 -i ; i ∈ {5, 6, 7, 8, 9}}. Three temporal scales proved to be sufficient for representing the UT-interaction actions and four scales showed no significant improvement. Although the actions recorded in such dataset are much more complex, the local movement that characterizes such actions occurs rapidly within a short time interval. From this observation, it is more useful to increase the histogram resolution rather than the temporal scales.

Table 4 and 5 show the confusion matrices obtained when assessing with UT-interaction, using its two different datasets. In average, it was obtained an accuracy of 81.6 and 78.3 for dataset one and two, respectively. In summary, the proposed approach achieves a relevant dynamic characterization of the different human interaction activities. However, such activities are often the result of combinations of complex motion patterns that may occur during a short time interval. Likewise, some of these interaction activities share local motion patterns that may lead to wrong predictions. For instance, interactions like "hand shaking", "pointing" or "pushing", share similar limb movements during certain temporal interval. Additionally, such scenarios highly increase the complexity of description, consider for instance a group of moving actors with a large variability in terms of appearance, interaction and background.

Finally, Table 6 reports the comparison of the proposed motion descriptor with other state-ofthe-art strategies. Some of these approaches achieve high accuracy rates in problems related with action recognition but they demand a complete processing of the video to compute the features that describe the sequence. For instance, the propagative voting approach [START_REF] Yu | Propagative hough voting for human activity recognition[END_REF] reports a computational complexity of O(N M )+O(W HT ), where N M is the number of matches and W , H, T is the spatial( width × height) and temporal video resolutions. Such number of matches is computed by using random projection trees, a precise strategy that results computationally expensive and prohibitive for online applications.

Other approaches combine different appearance and motion features that improve the perfor- mance in action classification tasks. Xiaofei et. al encode spatio-temporal points as enhanced BoW occurrence histograms after a preprossessing step (difference between consecutive frames). These histograms are combined with HoG to improve the action representation. However, the multiple steps of this approach result in a computationally expensive algorithm with particular parameterization for each of these steps, a limitation for specific scenarios and spatial configurations (appearance dependency). Particularly, this approach starts by computing frame differences to detect interactions in the video and define regions of interest. Then, it calculates 3d-SIFT points on the video. This computation requires the complete processing of fixed volumes to determine the keypoint candidates based on scale-time-space extrema detection. Such detection cannot be performed incrementally at each frame, and is applied on fixed time intervals of the video sequence. Then, 3d-SIFT descriptors (coded in 256 scalar values) are calculated on the detected points into a mid-level representation as visual words to compute a codebook of the actions. The codebook is based on a Multi-View Space Hidden Markov Models [START_REF] Ji | A view-invariant action recognition based on multi-view space hidden markov models[END_REF] that allows to learn time coherent fixed 3d-SIFT volumes. Although such mid-level strategy is computationally more expensive than classical Bag-of-Words, it allows to represent the actions for each temporal segment of volume computed for the 3d-SIFT. An additional step of video sequence characterization in this strategy consists in detecting regions of interest and split them into 16 subregions. Each of these subregions is then described by HOG histograms. Once both representations are computed, independent nearest neighbor searches are performed to obtain a likelihood measure of each feature w.r.t the closest trained action. Finally the histograms (3d-SIFT and HOG occurrence) are independently normalized and weighted according to the estimated likelihood. The two histograms are concatenated and mapped to a new nearest neighbor to obtain classification of the actions. In [START_REF] Mukherjee | Recognizing interaction between human performers using'key pose doublet[END_REF], a bipartite graph key pose doublets identifies interactions from a large multidimensional pose descriptor which requires expensive algorithms to match the graph patterns with the new sequences. The approaches presented in [START_REF] El Houda Slimani | Human interaction recognition based on the co-occurence of visual words[END_REF] and [START_REF] Ryoo | Human activity prediction: Early recognition of ongoing activities from streaming videos[END_REF] describe partial activities using histogram representations of some primitives computed at each frame but limited in term of accuracy. In contrast, the proposed

Approaches

Accuracy UT-dataset 1 Accuracy UT-dataset 2 Propagative voting [START_REF] Yu | Propagative hough voting for human activity recognition[END_REF] 93 91 Proposed approach 81.6 78.3 Daysy [START_REF] Cao | Action recognition using 3D DAISY descriptor[END_REF] 71 51 SIFT 3D [START_REF] Scovanner | A 3-dimensional sift descriptor and its application to action recognition[END_REF] 63 55 Slimani 2014 [START_REF] El Houda Slimani | Human interaction recognition based on the co-occurence of visual words[END_REF] 41 Ryoo 2011 [START_REF] Ryoo | Human activity prediction: Early recognition of ongoing activities from streaming videos[END_REF] 71.7 Mukherjee [START_REF] Mukherjee | Recognizing interaction between human performers using'key pose doublet[END_REF] 79.17 Xiaofei [START_REF] Ji | Multiple Feature Voting based Human Interaction Recognition[END_REF] 83.33

Table 6 Average accuracy for different reported state-of-the-art strategies. Although the propagation voting achieves better results in terms of accuracy, the match of features using random projection trees is computationally expensive. The Xiaoafei et. al. work integrates BoW occurrence histogram with HoG, representing again a high computational time to obtain an action representation. In contrast, the proposed approach produces a compact descriptor that takes into account different time interval depths by using the same source of primitives, i.e., a dense optical flow. Additionally, the recursive nature of the proposed approach makes this estimator is constantly updated so that partial sequences can be predicted. approach encodes motion orientations as histograms from a global perspective, as the region of interest, but also spatially localized from the spatially constrained representations. Such orientation histograms are summarized in a compact descriptor that involves the analysis of different time depth scales. Hence, the proposed descriptor robustly represents the spatio-temporal patterns of the activity and achieves a per-frame recognition. This proposed approach is suitable for real time applications because of its recursive construction and the partial description of the video.

Indeed, the proposed motion descriptor is quite simple and can be easily customized for realtime applications. The size of the frame-level action descriptor is d = N div × N φ × N stat × N α with N div the total number of subregions of the overlapped representation, N φ the number of orientation bins for the velocity, N stat the number of temporal statistics computed for each bin, and N α the number of time scales. The computational complexity of frame-level classification is C c = O(d). However, such figures are constant and the number of orientation bins N φ is the dominant factor. Although we used a dense optical flow field in our experiments, the proposed motion descriptor can be used together with any semi-dense optical flow method. In this work, we used a particular optical flow implementation based on the multiscale local jet nearest neighbor search. The local jet representation consists on characterizing each pixel by a set of derivatives estimated at different scales. Then pixel matching in adjacent frames is carried out by nearest neighbor search in a structured kd-tree space of local jet features. The computational complexity of the herein implemented optical flow is then

C f = O(W × H × d) + O(N log N ),
where the first term refers to the computation of the local jet feature (W and H being the image dimensions, and d the number of derivatives), and the second term to the nearest neighbor search, N being the number of points to match (which is at most W × H). Finally, the complete complexity for the local jet dense flow computation and the frame level classification is given by: C

d = C c + C f .

Discussion and concluding remarks

This article has introduced a novel motion descriptor consisting in the recursive computation of velocity orientation primitives that cover different temporal intervals and that are calculated on an overlapped partition of moving regions of interest. Inspired by visual systems, the proposed approach carries out a spatio-temporal analysis of the environment and determines salient information as those regions with coherent motion patterns. The approach, assessed in action recognition applications, demonstrated action prediction capability at any time, becoming then a good candidate to be used in real time applications, while being easy to implement and efficient in terms of accuracy and time.

Characterization of flow motion, as the orientation occurrence, has been largely exploited in action recognition tasks, mainly because of the relative independence of the visual appearance as well as the flexibility to describe very different motions [START_REF] Chaudhry | Histograms of oriented optical flow and binet-cauchy kernels on nonlinear dynamical systems for the recognition of human actions[END_REF], [START_REF] Ikizler | Human action recognition with line and flow histograms[END_REF]. However, these descriptors are in general restricted to represent invariant motions and therefore limited to specific applications. Also, they are commonly combined with appearance information that improves the description in specific scenarios but loses the flexibility of the motion flow information. The proposed approach is in contrast flexible and can represent a wide variety of real circumstances, from atomic gestures to interaction activities by computing cumulated statistics from the flow orientation histograms during variable time intervals. The different K temporal action periods (multi-frequency temporal representation) can be applied by adapting the hyper-parameter α as {α 1 . . . α k }, which enhances the action description for different motion models while preserving the robustness to represent actions in high scene variations. In fact, for a simple gesture recognition, the temporal descriptor requires few temporal scales, while for interaction and behavioural activities, the different scales have to cover the dynamic description.

In contrast to block-based representations [START_REF] Cao | Action recognition using 3D DAISY descriptor[END_REF][START_REF] Tabia | Motion histogram quantification for human action recognition[END_REF][START_REF] Ikizler | Human action recognition with line and flow histograms[END_REF], in which every block appearance representation of the video has the same relevance, the representation herein introduced increases the importance of several flow orientation patterns that remain at different subregions and during a particular time interval. The proposed motion descriptor has the capability to predict the actions at any time of the sequence by updating a motion descriptor from a multi-scale recursive framework. The computation time of the motion descriptor is acceptable, taking in average 10 ms to be updated at each frame with the current motion information. In this time testing was computed motion descriptor using 3 temporal scales, 32 bins per hitogram and a total of 15 subregions of the RoI. Additionally, the mapping of each motion descriptor to the SVM model at each time takes in average 11 ms. The experiments were carried out on a single core i3-3240 CPU @3.40 GHz. According to the types of scene and actions, the proposed motion descriptor can be designed as a trade-off between time/memory efficiency and classification accuracy.

This paper presented a novel approach that recognizes multiple human actions and classifies human activities as simple or complex. The descriptor consists of a series of statistics computed for different multiscale orientations and adapted intervals of time. The algorithm can run on line, thanks to its recursive nature and fast, even on a main stream architecture. The proposed descriptor achieved an average accuracy of 95% in the real surveillance dataset VISOR and 80% in the UT-interaction dataset. The proposed descriptor was mainly assessed in videos acquired with a stationary camera, yet it can be adapted to actions occuring in mobile scenarios, by adjusting the time intervals w.r.t to the camera motion, or by discarding the main optical flow clusters as representing the background. Future works include evaluation of the proposed descriptor in such scenarios. Likewise, this descriptor will be extended to recognition of interactive actions such as human group activities.

Fig. 1 .

 1 Fig. 1. Motion RoI segmentation and the spatially-constrained decomposition that together form a spatio-temporal representation. In (a) is computed the dense optical flow based on a multi-scale local jet representation. Such flow field characterization allows to bound the potential activities as Region of Interest (b). Each of these RoIs is then sequentially partitioned, up to obtain a spatial overlapped subregion representation (c).

Fig. 3 .

 3 Fig. 3. Pipeline of the frame-level action classification. The spatio-temporal histograms are quantified for each detected RoI and for each of the defined subregions from the overlapped representation. The motion descriptor is updated by the several statistics representing different temporal windows of analysis. The updated descriptor feeds a previously trained SVM and a label is returned for a particular RoI.

Fig. 4 .

 4 Fig. 4. The first row illustrates different examples of the human activities recorded in the ViSOR dataset. The second row shows different examples of activities in UT-interaction dataset

Fig. 5 .

 5 Fig. 5. On-line action recognition for different videos recording several human motion activities. The frame-level recognition is carried out by mapping the motion descriptor to the SVM model at each time. The action label with minimal distance to the hyperplanes is assigned to the corresponding RoI.

Table 4

 4 Confusion matrix for UT-interaction dataset No-1.Results are in % Category hs hg ki po pun pus Hand Shaking 90 0

  0 end for for each time t do for each sub-region of interest do calculate Histogram H t (φ) for each bin j of the H t (φ) Histogram do 1. Recursive mean:

Table 5

 5 Confusion matrix for UT-interaction dataset No-2. Results are in %.


Matthieu Garrigues

Antoine Manzanera

Fast Semi Dense Epipolar Flow Estimation

Optical flow computation consists in recovering the apparent motion field between two images with overlapping fields of view. This paper focuses on a subset of optical flow problems, called epipolar flow, where the camera moves inside a scene containing no moving objects. Accurate solutions exist but their high computational complexities make them non suitable for a large panel of real-time applications.

We propose a new epipolar flow approach with low computational complexity achieving the best error rate on the non dense KITTI optical flow 2012 benchmark and running 1000× faster than the second ranked approach. On a 4core 3GHz processor, our multi-core implementation computes a semi dense optical flow field of a 450k pixels image in 260ms. It is a significant advance in reducing the running time of accurate optical flow computation.

To achieve such results we rely on the epipolar constraints and the local coherence of the optical flow not only to increase accuracy but also to reduce computational complexity.

Our contribution is twofold. It is first, the acceleration and the accuracy increase of current RANSAC based visual odometry algorithms via the estimation of a robust sparse flow field, well distributed over the image domain. And then, the estimation of a semi dense flow field leveraging epipolar constraints and a propagation scheme to speedup the estimation and reduce error rates.

Introduction

With the raise of augmented reality, virtual reality and robotics, capturing the geometry of a real-world 3d environment has attracted considerable research efforts in academic and industrial laboratories.

The problem consists in computing the 3d localization of objects observed using an on-board sensor. The ultimate goal of this challenge is to achieve the best accuracy while reducing the manufacturing cost and power consumption [START_REF] Sansoni | State-of-theart and applications of 3d imaging sensors in industry, cultural heritage, medicine, and criminal investigation[END_REF].

As of the year 2016, the most precise sensors are LI-DARs. They measure the depth of neighboring object by timing the round trip of a light pulse. Their main disadvantage is their high price tag and high power consumption.

Much cheaper than LIDARs, active structured-light 3D scanners are well-spread: the Microsoft Kinect V1 [START_REF] Zhang | Microsoft Kinect sensor and its effect[END_REF], and other portable devices such as Google Tango [6]. They work well in indoor and small range environments but their accuracy drop under the sunlight and large distances. This makes them unsuitable for autonomous driving applications for example. The second problem of these sensors is their high power consumption due to the emission of the structured light.

The cheapest sensors are the RGB cameras. However, they do not provide depth information, then different methods to recover it were proposed. They usually involve one or two steps: First, if they are not already known, the estimation of the relative camera poses (also known as visual odometry), and the optical flow computation. The power consumption of such systems is smaller than LIDAR and structured-light scanners but their accuracy highly depends on the texture of the scene. Furthermore, the higher complexity of the problem makes it harder to build fast and accurate applications, especially for the non-calibrated case and where the relative poses of the different points of view are unknown.

In this paper, we focus on epipolar flow. In this paper, we focus on epipolar flow. It consists in the estimation of a disparity map from an image pair captured by a camera moving inside a static scene. Despite its inability to capture the depth of moving objects, it is useful in applications like 3D scene reconstruction. It also has two advantages over stereo-vision done with a pair of aligned cameras: First, it only uses one camera and second, it is more flexible with respect to the viewpoint variation.

We propose a novel approach to compute the optical flow between two images. It is faster and more precise than the current state of the art algorithms in the static scene/moving camera case. According to the KITTI optical flow bench-mark [START_REF] Geiger | Are we ready for autonomous driving? the KITTI vision benchmark suite[END_REF] 98.3% of the estimated flow vectors have a Euclidean distance to the ground truth inferior to 3 pixels and, in average, it covers 50% of the image pixels. It is ranked first for the partial estimation in this benchmark, while being 1000× faster than the second. Our following three contributions span over the different stages of the epipolar flow pipeline:

• A well distributed and accurate sparse flow vector field estimation that increases robustness and reduces runtime of RANSAC based fundamental matrix estimation.

• A fast and almost error free estimation of a semidense optical flow, narrowing the search to the epipolar lines.

• An error filter relying on the Lucas-Kanade optical flow [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] and a simple local coherence criterion that filters most of the erroneous flow vectors.

• A fast open-source C++ implementation optimized for multi-core CPU and processing a KITTI image pair in 260 milliseconds on a 4-core 3GHz processor. We are currently submitting the code to the open source (under the MIT licence) C++ image processing library Video++ [START_REF] Garrigues | Video++, a modern image and video processing C++ framework[END_REF].

The paper is organized as follows. In Section 2, we present how our approach is related to the state of the art, and also how it differs from it. Then in Section 3, we go through the notation used in this paper. In Section 4, we describe our improved fundamental matrix estimation and in Section 5, we present the semi dense optical flow estimation. Finally, we evaluate our approach with the KITTI optical flow benchmark in Section 6.

Related Works

During the last years, many works were conducted to improved the quality and/or reduce the computation time of optical flow from an image pair. The KITTI optical flow benchmark references and ranks 78 methods. Competing algorithms can rely on 3 kinds of additional information: First, they may estimate and make use of epipolar constraints, then they may use stereo image pairs, and finally they may use a sequence of more than two images. On Figure 1, we draw the distribution of the algorithms competing on the partial estimation section of this benchmark. We observe that a high proportion of algorithms have running time ranging from 10s to 1000s, and error rates ranging from 4% to 10%. Accurate and fast running algorithms are fewer, with only 5, including ours, running under 1s and with error rate lower than 10%.

The best approaches often make hypothesis about the 3D structure of the scene: In [START_REF] Bleyer | Surface stereo with soft segmentation[END_REF][START_REF] Yamaguchi | Continuous Markov random fields for robust stereo estimation[END_REF][START_REF] Yamaguchi | Robust monocular epipolar flow estimation[END_REF][START_REF] Zhang | Local stereo matching with 3D adaptive cost aggregation for slanted surface modeling and sub-pixel accuracy[END_REF][START_REF] Vogel | 3D scene flow estimation with a piecewise rigid scene model[END_REF], it is considered as a union of slanted 3D plane portions (facets). This allows to shift the problem from the pixel scale to the superpixel (projected facet) scale, significantly reducing the number of unknowns. These approaches formulate a global energy function based on the brightness constancy and other data, with regularization terms. To find a solution close to the global minimum, they rely on an energy minimization technique like particle convex belief propagation [START_REF] Peng | Convex max-product algorithms for continuous MRFs with applications to protein folding[END_REF], graph cuts [START_REF] Vogel | 3D scene flow estimation with a piecewise rigid scene model[END_REF], or customized iterative algorithms [START_REF] Yamaguchi | Robust monocular epipolar flow estimation[END_REF] to jointly estimate the super-pixel segmentation and the associated slanted facets. These techniques have the advantage of providing an accurate dense optical flow but their computation time remains high: from 10s to several minutes per image. While these solutions focus on accuracy rather than running time, accelerating the estimation of optical flow to real time (> 10f ps) processing also drew much research interest. In [START_REF] Plyer | Massively parallel Lucas Kanade optical flow for real-time video processing applications[END_REF], the authors present eFOLKI, derived from the multi-scale iterative Lucas Kanade [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] algorithm. To speedup the computation, they reduce the number of pixel interpolations by wrapping the whole image after each iteration of the gradient descent. To increase accuracy, they use a dynamic integration window size, to avoid oversmoothing the optical flow field. Running on the GPU, this is one of the fastest optical flow computation of the KITTI optical flow benchmark, but it is ranked 60th in terms of accuracy.

As shown in Figure 1, our proposal is distinguished by a low running time and the lowest error rate. To achieve this, it first combines several ideas from the state of the art:

• It constraints the estimation of optical flow to the epipolar lines as in [START_REF] Yamaguchi | Robust monocular epipolar flow estimation[END_REF][START_REF] Yamaguchi | Efficient joint segmentation, occlusion labeling, stereo and flow estimation[END_REF].

• It uses a fast local gradient descent minimizing an SSD distance between two patches to compute each optical flow vector, similarly to Lucas Kanade [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF].

• Its parallel implementation takes advantage of a multi-core CPU architecture as in [START_REF] Plyer | Massively parallel Lucas Kanade optical flow for real-time video processing applications[END_REF] which compute the optical flow on a GPU.

The low running time of our approach is also partly due to the region growing algorithm that propagates and refines optical flow vectors. Unlike the leading algorithms of the KITTI benchmark, this step leverages local coherence not to build an expensive global energy minimization but to reduce running time and errors.

Another particularity of our solution is the use of the Lucas-Kanade algorithm not to compute actual optical flow vectors, but to help filtering the errors.

Notations

In the following, we will use the following notations:

• I 1 and I 2 are the two input images.

• A 3D point X is projected on images I 1 and I 2 at the 2D pixel coordinates x 1 and x 2 respectively.

• x is the 3D homogeneous coordinates of a 2D vector x.

• F is the 3 × 3 fundamental matrix, relating x1 and x2 .

Fundamental Matrix Estimation

Generic optical flow algorithms have to estimate, for each pixel, two unknowns: the displacement along the two dimensions of the image. They always face two major challenges: repetitive texture causing erroneous matches, and the large dimension of the search space increasing the running time.

However, in a static scene captured by a moving camera, the optical flow projected on the focal plane is only related to the distance of the objects and the camera motion. If the camera rotation and translation are known, only the 1D disparity of each pixel remains to be estimated. The search space is then reduced from a 2D domain to a line, called the epipolar line.

This greatly simplifies the computation of the optical flow. First, because the probability that more than one similar pixels appear is lower in a smaller space, thus reducing the number of errors. And second, it reduces the number of comparisons required to find the best match, thus speeding up the search.

The camera motion (as well as its intrinsic parameters) is usually encoded as the fundamental matrix F , with the following property: if x1 and x2 are the homogeneous coordinates of the projection of the same 3D point X in the first and second image respectively, we have:

xT 2 F x1 = 0 (1)
In other words, it means that X, its two projections and the two optical centers lie on the same 3D plane. When x 1 and F are known and x 2 is unknown, the coefficients of the line where x 2 lies can be computed as follows: if l 2 = xT 1 F , we get l T 2 x2 = 0 which defines a line in the I 2 coordinate space, and allows us to reduce the matching of a 2D point to a search along a single 1D line.

The fundamental matrix also provides the common point of all epipolar lines, which is usually called epipole and denoted e 1 (resp. e 2 ) for the first (resp. second) image :

ẽT 2 F = 0 (2)
F ẽ1 = 0 (3)
The estimation of the fundamental matrix F usually relies on a set of correspondences between pixels of I 1 and I 2 .

Theoretically, only seven correspondences are needed to estimate F , but it is common to rely on few hundreds to increase the robustness to matching errors. There are existing solutions [START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF][START_REF] Richard | In defence of the 8-point algorithm[END_REF] to estimate F from a set of correspondences. Their accuracy and runtime depend on two criteria:

• The precision of the 2D/2D correspondences.

• The uniform distribution of the correspondences over the image domain.

Overview

The Fundamental matrix estimation pipeline begins with the matching of two FAST [START_REF] Rosten | Machine learning for highspeed corner detection[END_REF] keypoint sets, extracted from the two images. Grid indexing on the keypoint sets speeds up the search. Then, the displacement vectors are refined using a pyramidal Lucas-Kanade [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] scheme. A filter is applied on the set of resulting matches to reduce the number of errors. The fundamental matrix is finally estimated with a classical method [START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF][START_REF] Richard | In defence of the 8-point algorithm[END_REF].

Evaluation

To evaluate the precision of the fundamental matrix associated to an image pair, we estimate the deviation of the epipolar lines from the ground truth optical flow.

Using the set of pixels with ground truth vectors GT provided by the KITTI optical flow benchmark, we define the fundamental matrix F error E F as the maximum distance between the epipolar line associated to a pixel x 1 and its ground truth match x 2 .

E F = max (x1,x2)∈GT |x T 2 l| l 2 a + l 2 b , (4)
with:

l = F x1 =   l a l b l c   . (5)
In the following, we analyze the impact of several parameters on the fundamental matrix error and on the runtime of the whole pipeline.

Sparse FAST to FAST keypoint matching

The first step of the fundamental matrix estimation is the computation of a sparse optical flow vector field. Its role is to feed the fundamental matrix estimation and to provide seeds for the semi dense epipolar flow estimation (Section 5).

To compute a sparse optical flow vector field, lots of methods rely on the fact that the displacement is small and can be recovered by locally optimizing a SSD distance via a gradient descent [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF]. The quality of these methods highly depends on the magnitude of the displacements, even in a multi-scale framework [START_REF] Bouguet | Pyramidal implementation of the affine Lucas Kanade feature tracker description of the algorithm[END_REF]. In our work, to match large displacement as well as small displacements, we preferred to match the FAST keypoints of I 1 against the FAST keypoints of the I 2 image. This way, we rely on the keypoint repeatability instead of the small displacement assumption. For each keypoint selected in the first image, we search for the keypoint in the second image that has the smallest SSD distance to it (The SSD is computed using a 11 × 11 neighborhood patch). Thanks to the keypoint detector repeatability, it can be expected that most of the keypoints in the first image will also be detected in the second image.

However, the FAST detector is not appropriate to feed a fundamental matrix estimator: the distribution of the FAST keypoints highly depends on the content of the image, as the FAST detector is not designed to guarantee an even spatial distribution, which is detrimental to the estimation of the fundamental matrix.

In order to correct this distribution problem, we set up the following blockwise selection strategy: in each image block of a N c × N c grid, we select the FAST keypoint with the highest score, as long as it is higher than a threshold keypointT h. This blockwise selection strategy ensures that only one keypoint per block gets selected. This way, keypoints are more evenly distributed over the image domain and capture more motion information, thus improving the estimation of F .

In spite of these advantages, such blockwise selection alters the repeatability of the FAST detector and causes some erroneous matches. A filtering strategy is proposed in Section 4.4 to remove the errors of this matching step.

We tested the fundamental matrix estimator with all couples of parameters N c and keypointT h, and averaged the measures on the 50 first images of the KITTI dataset. The results confirm our hypothesis: Figure 2 shows that thanks to the better distribution induced by the blockwise strategy, a smaller grid resolution N c can be used to reduce the runtime by an order of magnitude, without increasing the error on the estimation of F .

Speeding up the F Estimator with Erroneous Matches Filtering

Because the blockwise FAST keypoint strategy alters the repeatability of the keypoints, some keypoints in the first image may not be detected in the second image and sometimes matched with some other similar keypoints, leading to erroneous matches.

These errors are usually detected and filtered out using a RANSAC estimator of the fundamental matrix. However, RANSAC iterations of the F estimator are time-consuming, so the fewer outliers we have, the faster the F estimator. Then, to save some of these expensive iterations, we filter out matches diverging from their local median displacement using the following filter:

A flow vector v is kept only if it respects the following constraint:

||v -med|| < medT h, (6)
with med the median flow vector calculated within the image block containing v in the Rf × Rf partition grid. Figure 3 shows the performances of a set of runs of the full F estimation pipeline with varying medT h parameters. Lower runtimes correspond to smaller medT h values. It can be observed that our filter is able to reduce running time by approximately 30% without impacting the error on F . The variance along the F error is due to fluctuations in the RANSAC precision. Because the sparse keypoint matching computes correspondences between FAST keypoints, their precision is not subpixelic. This reduces the precision of the fundamental matrix estimation. To overcome this problem, we refine the matches with a two scale Lucas-Kanade gradient descent [START_REF] Bouguet | Pyramidal implementation of the affine Lucas Kanade feature tracker description of the algorithm[END_REF].

Fundamental matrix estimation

From the set of refined matches, the fundamental matrix can be estimated with one of the state of the art estimator wrapped in a RANSAC scheme, to be robust to the remaining outliers. Despite the fact that they all benefit from our evenly distributed and error-filtered set of optical flow vectors, the runtime and error of the RANSAC scheme is highly dependent on the inlier acceptance threshold ransacT h.

On the presented experiments, the fundamental matrix was estimated using the 8-point algorithm [START_REF] Longuet-Higgins | A computer algorithm for reconstructing a scene from two projections[END_REF] with the RANSAC scheme thanks to the cv::findFundamentalMat OpenCV function [3]. Figure 4 shows the influence of the RANSAC threshold on the runtime and on the F error. It can be observed that up to the value 0.3, increasing this parameter reduces the runtime without impacting the F error.

Guided Semi Dense Optical Flow Computation

We present in this section how, using the epipolar constraints, we guide the estimation of the optical flow to increase robustness and decrease computation time.

Disparity estimation and propagation

The disparity D(x 1 ) that we are looking for minimizes for a given pixel x 1 the SSD distance between a patch centered on a pixel in I 2 and the neighborhood patch of x 1 in I 1 . Thanks to the epipolar constraint, the domain of this minimization is reduced to the line l 2 , which can be parameterized as follows:

l 2 (x 1 , d) = e 2 + dv (7)
with d ∈ R the disparity, v a direction vector of the epipolar line and e 2 the coordinates of the epipole in I 2 .

The computation of the disparity field D can be formulated as the following minimization:

D(x 1 ) = arg min d u∈[-3,3] 2 I 1 (x 1 + u) -I 2 (l 2 (x 1 , d) + u) 2 (8)
To compute D, we propose the following algorithm:

Initialization. For all sparse 2D optical flow vectors previously (section 4.3) computed for the fundamental matrix estimation, we save their corresponding disparities in the 2D disparity field at their location. We call them "seed disparities" in the following.

Disparity optimization and propagation. Once the disparity field initialized, we refine and propagate the seed disparities as follows: for each pixel on a propagation front, we refine its disparity by a gradient descent on the epipolar line locally minimizing the SSD distance (equation 8).

After processing a pixel we enqueue each one of its c8neighbors y i 1 i=1..8 if it meets the two following conditions:

• The local gradient norm is superior to the minGradient threshold.

• The disparity at point y i 1 has not already been computed or is too different from the disparity we want to propagate (absolute difference greater than dispP ropT h).

The first criterion prevents the propagation on textureless regions while the second avoids searching twice for the same local minimum.

Note that because there are several seeds, several propagation fronts coexist, and then the same pixel may be examined several times. When re-examining a pixel, we save the new disparity only if it reduces the SSD distance.

Speeding up the search on multi-core processors. The advantage of this propagation scheme is that the processes attached to different seeds are independent and can run in separate threads, as long as they do not process simultaneously the same pixel. This allows a significant speedup on multi-core processors.

Error detection and filtering

The optimization of the disparity field presented in the previous section restricts its search domain to the epipolar lines. To verify the validity of each optical flow vector estimated at this step, we propose to check if they actually minimize the SSD distance in all the directions.

We do this by running one iteration of the Lucas-Kanade optical flow algorithm [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] on each estimated vector. If the computed optical flow vector does not correspond to a local minimum in the 2D space, the Lucas-Kanade algorithm will diverge from the epipolar line.

Errors are then detected when at least one of the following conditions is met:

• Non local minimum: If the distance between the destination of the optical flow vector and the epipolar line is greater than eth.

• Local incoherence: If the distance between a vector v and the vectors from its N v × N v neighborhood is greater than dth for at least dp% of its neighbors, it is considered incoherent. The best results were obtained with N v = 15 and dp = 60.

To evaluate the performance of our filter, we use the following protocol: For each parameter pair {eth, dth}, we count the proportion of flow vectors that are rightly or wrongly classified as an error, the "true" errors being defined as the vectors which differs from the KITTI ground truth of more than 3 pixels. Figure 5 shows the evolution of these two proportions over the different filter configurations. To reduce the parameter space of the evaluation, we set a proportional relation between the two parameters as follows: eth = dth/4.3.

Note that the use of Lucas-Kanade [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] here is novel: we not only use it to refine the flow field, but also to decorrelate the erroneous flow vectors, by spreading the wrongly matched points (which stick to the epipolar line) in inconsistent directions. This highly helps to better filter the errors, and other optical flow methods could benefit from it.

Second propagation

Error filtering creates holes in the optical flow field. And while large holes are hard to fill, optical flow in small holes can be recovered with satisfying precision from neighboring flow vectors. We therefore replace missing vectors by the average of the vectors located in the 7 × 7 neighborhood. In our experiments on the KITTI dataset, this method could recover 15% of the image pixels with a negligible error rate increase.

Results and comparison with the state of the art

We evaluate our approach on the KITTI Optical Flow 2012 benchmark. This base contains a collection of image pairs acquired from a forward looking camera embedded on a car and their ground truth optical flow computed from LIDAR data. The dataset features several types of camera motion like forward translations, or rotations.

The table 1 presents the ranking of the leading algorithms of the benchmark with respect to the error rates, for the non-dense optical flow computation. Our approach ranks first, provides error rates 1.5× smaller and running time 1000× smaller than the second ranked one [START_REF] Vogel | 3D scene flow estimation with a piecewise rigid scene model[END_REF]. It is worth noting that the latter covers 100% of the image pixels while ours covers 50%. The best method having similar running time [START_REF] Senst | Robust local optical flow estimation using bilinear equations for sparse motion estimation[END_REF] uses a GPU, covers only 15.26% of the pixels and has error rates two times higher. Figure 6 presents the optical flow on a KITTI image pair and Figure 7 shows the errors according to the ground truth.

Conclusion and future works

We proposed in this paper an algorithm to compute the camera motion and the optical flow in the case of a mov-Table 1. KITTI optical flow 2012 ranking of the seven best algorithms with respect to the error rate (where the errors correspond to estimated vectors whose difference with the ground truth is greater than 3 pixels). The error rate is averaged on the estimated pixels. Our approach (FSDEF) computes an optical flow field with fewer errors and has a running time which is three orders of magnitude lower than the second ranked approach. The only algorithm with lower (-11%) computation time is BERLOF [START_REF] Senst | Robust local optical flow estimation using bilinear equations for sparse motion estimation[END_REF], which uses a GPU and covers only 15% of the pixels. For each algorithm, Out-Noc represents the error rates of the non occluded pixels, Density is the proportion of estimated pixels and Runtime the processing time in seconds for one image pair.

Method

Out ing camera and a static scene. Our approach provides a semi dense flow field, covering in average 50% of the image pixels, with an error rate smaller than the previously first ranked approach on the KITTI optical flow benchmark, while running 1000× faster.

To obtain such results we optimized each steps of the pipeline with two goals in mind: low running time and when possible, better accuracy. First, by ensuring a good spatial distribution of keypoints and by prefiltering outliers, we could accelerate visual odometry by an order of magnitude while keeping the best accuracy for the fundamental matrix estimation. Then, by leveraging the epipolar geometry and local coherence, we proposed a fast computation of the optical flow and a filter able to filter out 95% of its errors.

Even if it achieves the best error rate on the KITTI optical flow benchmark, our approach leaves room for many improvements using ideas from the state of the art. For example, a facet model of the scene could be used as in [START_REF] Yamaguchi | Robust monocular epipolar flow estimation[END_REF], or a priori knowledge about the 3D structure of the scene as in [START_REF] Vogel | 3D scene flow estimation with a piecewise rigid scene model[END_REF]. However, these techniques often rely on expensive global energy minimization and it remains a challenge to leverage them without impacting the running time.

Figure 1 .

 1 Figure 1. Error rates vs running time of the algorithms referenced by the KITTI optical flow section "partial estimation", on a logarithmic scale. Colors encode the density of the computed optical flow. Only 5 competitors have both a running time under 1s, and an error rate lower than 10%.

Figure 2 .

 2 Figure 2. Impact of the keypoint grid resolution on the runtime of the fundamental matrix estimator. We used a linear interpolation to generate a dense mapping from our set of experiments.

Figure 3 .

 3 Figure 3. Efficiency of the Erroneous Matches Filtering

Figure 4 .

 4 Figure 4. Impact of the RANSAC threshold on the F error and on the runtime of the F estimator

FalseFigure 5 .

 5 Figure 5. Accuracy of the proposed error filter.

It estimates small displacements as well as large ones.

It ensures a good distribution of 2D/2D correspondences over the image domain, increasing the accuracy of the estimation

4. It realizes a good trade-off between accuracy and run-ning time on a multi-core processor.In the remaining of this section, we first give an overview of the algorithm, then go through each part into deeper details, and finally benchmark its accuracy and speed on the KITTI optical flow benchmark.