See before you see: Real-time high speed motion prediction using fast aperture-robust event-driven visual flow

Optical flow is a crucial component of the feature space for early visual processing of dynamic scenes especially in new applications such as self-driving vehicles, drones and autonomous robots. The dynamic vision sensors are well suited for such applications because of their asynchronous, sparse and temporally precise representation of the visual dynamics. Many algorithms proposed for computing visual flow for these sensors suffer from the aperture problem as the direction of the estimated flow is governed by the curvature of the object rather than the true motion direction. Some methods that do overcome this problem by temporal windowing under-utilize the true precise temporal nature of the dynamic sensors. In this paper, we propose a novel multi-scale plane fitting based visual flow algorithm that is robust to the aperture problem and also computationally fast and efficient. Our algorithm performs well in many scenarios ranging from fixed camera recording simple geometric shapes to real world scenarios such as camera mounted on a moving car and can successfully perform event-by-event motion estimation of objects in the scene to allow for predictions of upto 500 ms i.e. equivalent to 10 to 25 frames with traditional cameras.


Introduction
Optical flow is the measure of motion of an object projected on to the image plane of a camera. It is one of the fundamental steps needed for understanding a dynamic visual scene and has taken an even important role with newer applications such as autonomous driving vehicles [16], drones, action perception during user interactions [14] in robots and traditional applications like video editing [15] and stabilization. Because the visual sensing has traditionally been based on image acquisition at fixed time intervals, the computation of optical flow has been based on finding features that move across two or more consecutive images. Since the intensity of light received on the sensor is the most basic feature, the first principle approach for measurement of optical flow is given by the 'brightness constancy assumption' that assumes that the brightness of an object moving across the camera remains constant over short internal of time. Ideally this time interval should be infinitesimal, but practically, for the traditional cameras, this means the time between two recorded frames. This constant instantaneous brightness assumption forms the basis for the earliest algorithms such as those proposed by Horn and Schunk [4] and the Lucas-Kanade (LK) algorithm [5]. This has been further expanded to 'constant feature assumption' where complex features or descriptors are extracted [6] and tracked over multiple spatial scales [19]. With the advancements in convolution and deep neural networks, a number of new algorithms using these approaches have been proposed to compute visual flow [20,17,18]. Some of these methods even propose tackling optical flow computation as a learning problem [21]. While these approaches intend to achieve high accuracy using the improving computational power of GPUs and FPGAs, the fundamental problem of fast sensing and image processing still poses a hinderance towards using such techniques as part of a larger perceptive autonomous system. The new generation of dynamic visual sensors [1,2,3] might be able to fill in this niche application space by virtue of their fast, accurate sensing of light with high temporal precision. In this paper, we propose an algorithm designed for use with one such type of sensor [3]. Event-driven sensors have evolved over the last few years as possible succes-D R A F T sors to frame based classical cameras, especially for visual sensing in research areas that require high precision over a large temporal dynamics range like robotics [23,25,22,24], autonomous vehicles [26] and navigation in drones [27]. As these sensors provide precise motion information due to the inherent design of the pixels, they are ideal for fast visual flow computations. A number of methods have been proposed to compute visual flow using event based sensors. As events in the event-driven sensors are essentially encoding the light intensity captured by the pixels, algorithms based on the original image based Lucas-Kanade method have been proposed [7]. While these event-driven derivatives are fast, they cannot achieve the same accuracies as the frame-based variants due to the loss of information in conversion from intensity to events. Several algorithms are designed specifically to take advantage of the temporal nature of event-driven paradigm [8,9]. These algorithms use the spatiotemporal structure of events to estimate the flow by fitting a surface (usually a plane) and compute the normal of this surface as flow estimate. These algorithms maybe classified under the label of 'plane-fitting algorithms'. While these algorithms have improved accuracy of event flow, they are limited to computations of local dense flow. Further, the flow obtained is always computed as orthogonal to the edge irrespective of the direction of true motion. Thus, the flow computation is susceptible to the gradient of the edge. This problem is referred to as the aperture problem. The only way to tackle the aperture problem with a traditional plane-fitting method is to increase the size of the spatial neighborhood around the events when fitting the plane but this can lead to errors as the true size of the object is unknown and the shape of object may not be remain linear. A recent algorithm has been able to avoid this problem using constrained statistical properties of the object but it is computationally too intense to be used in real time and is only valid for object with closed form [10]. Another recent method for computing event-driven visual flow uses a spatio-temporal window of events and performs histogram matching of the event clusters to estimate the direction and speed of object. Thus, the current state-of-the-art algorithms lose the temporal dynamics of the input sensor events as they require pooling of events over a temporal and spatial window to avoid aperture problem.
Here we propose a new event-driven algorithm to solve aperture problem using multi-scale spatial pooling that uses the local erroneous flows computed at the lowest scales and corrects their direction towards the true direction of motion of the object. We mathematically prove that because of the specific properties of the plane fitting algorithms, pooling the fast but erroneous local flows over an appropriate spatial scale can correctly estimate the true direction of the object. Further, the estimation of this spatial scale can be computed at every event independently without any a-priori knowledge about the shape and size of the objects in the scene and is independent of any global motion of the camera. The proposed algorithm can perform in myriad of scenarios. Finally, this flow rectification allows us to perform very low-level event predictions i.e. when and where should new events appear according to the observations. We show via experiments that we can estimate on the fly, locations and velocities of moving objects up upto 500ms ahead in the future. Such prediction can be implemented for solving visual tasks such as collision avoidance and tracking.

Methods
The algorithm proposed in this paper uses multiscale pooling found in biological visual system in higher animals for hierarchical object recognition. The basic idea here is to perform local, fast flow measurements which might be incorrect in their direction estimations but are relatively reliable in amplitude estimates and then correct the direction estimates using global amplitude information. Figure 1 shows the principle idea motivating the correction procedure explained in the next section. Let us assume the most ideal case suited for the plane fitting method: a single bar moving in front of the camera generating a perfect event plane in the [x, y, t] space. If the bar is oriented orthogonal to its direction of motion Fig 1(a), the estimate of the velocity computed using the plane fitting method [8] (Fig 1(d)) would be equal to the true velocity U. But, if the bar is now rotated (b) by an angle θ, the velocity estimate of the flow from plane fitting is U n = U T n.n, n being the unit normal to the bar. The signed magnitude of this flow can be given by:

Multiscale pooling
This shows that the plane-ftting based estimated flow is equal to true direction of motion when the magnitude of the estimate is maximum, i.e. the cosine is maximum in Eq. (1). It is important to note that the normal n, without additional assumption, can have two directions -D R A F T Figure 1: (a) and (b) show an oriented edge moving across the sensor in true direction U and the predicted local flow U T n by fitting the plane over events in [x, y, t] space as in (d) and (e). The magnitude of the normal velocity component estimated by the plane fitting method is related to the orientation of the edge and true motion direction as U T n = |U| cos (θ). This relationship can be extended to a larger complex shaped object by linearizing it using multiple small edges (c) over small spatial region and performing plane fitting over each local edge (f). (c) The true flow direction can be estimated by finding the correct spatial size σ corresponding to the maximum mean magnitude |U n |.
namely either one of the two directions along the line orthogonal to the bar. However, if we are considering the temporal surface defined in [8] (as shown in figure 1(d-f)) as a bi-dimensional function t of (x, y), where the gradient of t allows us to define n as its unit direction vector then t is always increasing in the direction of the motion (i.e. the directional derivative of t along U is increasing) and we always have θ ∈ [− π 2 , π 2 ] or equivalently U t .n ≥ 0. We can generalize the observation in Eq (1) to more complex objects using this property of the plane-fitting flow computation. Figure 1(c and f) shows one such example case: let us consider a contour of a random shape moving with velocity U. We can approximate this shape as a set of line segments. For each pixel/event of each segment, the plane fitting method is estimating U n . If we consider a spatial neighborhood σ around a random pixel (example : green dot in (c) ) -for which we have estimated its normal velocity, the mean speed (i.e. the amplitude of the mean velocity) computed within σ is defined as: where K i is the length of the i th segment in pixels within σ and with the assumption that all the pixels are contributing in the mean flow estimation. If we assume that within this spatial neighborhood there lies a line segment j such that it is oriented relatively closest to the true motion direction (i.e. θ is minimal and ideally θ j = 0 when it is oriented orthogonal to the true velocity), we can find an upper bound for |U n |: Since the local mean speed is upper bounded by the amplitude of the velocity that is "most" collinear to U, the larger the |U n | we get from a given σ, the closer we are to U i.e. the σ leading to the largest |U n | is the "right spatial scale" for which |U − U n | is minimized. As we do not know the true velocity U, U m becomes our next best reference for U. According to this observation, for a given flow estimate, we define the problem of correction as the minimization problem of finding the neighborhood scale, σ, for which the cluster of flow estimates whose mean magnitude is close to the theoretical maximum |U| ≈ U m as described previously. Thus, for given neighborhood σ, we define the error function as: We then have according to (3): Since 0 ≤ |U n | ≤ U m , the problem of finding the right σ is equivalent to the minimization problem The above equations show that finding the scale with maximum mean magnitude is equivalent to finding the scale which best estimates the direction of true global flow. Thus, we only require to compute the flow over the smallest scale once, and perform the above maximization over larger spatial scales to get the true global motion direction. The proposed algorithm can therefore be divided into three steps. First, we compute local flow for each event using plane fitting. Second, we search for a spatial scale for which the mean magnitude of these local flows is maximized. Third, we calculate the mean direction for the flows in this scale and assign the direction to all the local flow events within this scale.

Implemented Algorithm
The steps involved in the implementation of the flow are described in Algorithm 1. The local flow was computed using an iterative implementation of the plane fitting flow as in [12]. Some minor changes are introduced to the original implementation in in [12] to improve performance. Firstly, to improve the accuracy of the flow and remove noise, we add an error correction step to ensure better accuracy of the plane fitting by computing the number of inliers (events that are within a certain distance from the fitted plane). If the number of inliers is more than half the total points used to fit the plane, we consider the fitting to be good and the flow estimate to be reliable. This improves overall efficiency and noise robustness as the rectification is only performed on valid flow events. To further avoid older events from corrupting flow estimates, we added a temporal history limit such that the correction was performed using events that occurred within a certain time (t past ) from current event. Table 1 lists the parameters values used to estimate flow for datasets used the experiments and results in Section 4.
Algorithm 1 Multi-scale aperture robust optical flow 1: for each event x, y, t do 2:

COMPUTE LOCAL FLOW (EDL):
3: Apply the plane fitting algorithm as in [8] to estimate the plane parameters [a, b, c] within a neighborhood of (x, y, t). for each (x i , y i ) in the neighborhood N do 7:t = (ax i − x) + (by i − y) 8: if |t i −t| <v 2 then

Parameter
Value Local flow Filter size N 5 pixels Inlier percentage 50% Rectification Spatial range σ 0 to 100 pixels in steps of 10 Temporal limit t past 5 msec

Experiments and results
The performance of the algorithm was measured in different scenario to test its effectiveness over the plane fitting method. The results is divided into two D R A F T  The EDL flow (red) however leads to a larger variance and almost a uniform distribution. Even with only one object in the scene (bottom row), EDL flow gives rise to two modalities but ARMS gives a single peak at 3π/2.

Camera fixed, multiple objects
Next, we tested the robustness of the multi-scale pooling in case when more than one object moving in front of the camera. To do this, we recorded two simple objects (two squares) moving across the camera in opposite directions. We also have a stationary object in the scene that may lead to noisy events. The experiment shows that the spatial pooling is not affected by multiple objects and the algorithm can find the correct scales for each object independently. Further, when the objects cross each other close by, the algorithm is robust enough to recover the correct directions. directions. This, is corrected by ARMS so that we get two distinct peaks in the direction histograms. As the objects collide and cross each other, the EDL becomes slightly worse and the peaks shift whereas the ARMS flow distribution remains invariant (Fig 3  [middle row]). Finally, as the objects move further, and we only have one object, the distributions becomes similar to the one in Exp 4.1.1 with single moving object. Again, while EDL gives two peaks for each of the edge orientations, we get a single peak from ARMS indicating the global motion direction.

Real world scene -Camera mounted on moving car
The flow rectification is also assessed through a real world scene in which the event-based camera was mounted on a car moving through traffic along the streets of Paris. The flow obtained from algorithm corrects the local perpendicular flow to provide a better global flow especially when the car is making turns, where the whole scene should have the same global flow direction. The optical flow corrections can improve the flow directions when the car is turning, making all events predicting the correct direction of the global motion. Further, the combination of speed and flow directions can easily segment objects moving independently from the car. Figure 4 D R A F T shows the EDL and ARMS flow for different traffic conditions. The bottom row shows interesting points (marked by black rectangles) in the scene where the ARMS flow successfully corrects erroneous directions of the EDL. These show that the spatial scale estimation works correctly even in a cluttered environment and large motion events. Further, direction estimates of independent moving objects such as cars is not affected by the global motion.

Event based prediction using ARMS flow 4.2.1 Trivial Case
The corrected direction estimates using ARMS flow can greatly improve the prediction of rigid object over traditional plane fitting methods. Figure 5 shows the actual future events (green) and the predicted events for EDL (red) and ARMS (blue) flow using events that occurred 250 msec in the past. The figure shows that using ARMS flow, all the predicted events of the square form another square but if the directions are not the same as in case of the EDL, the predicted shape is not rigid anymore and does not form a square. To quantify the performance of the two flows, we compute how well the predicted events from local and corrected flow maintain the rigidness of the object. That is, we compute the affine transformation needed to map the predicted events to the actual events. To simplify, we assume zero rotation and perform only translation and scaling. The graphs in figure 5 show the scaling and translation needed for the EDL and ARMS flow for a sequence of 360 msec broken into event clusters of 20 msec each. A perfect prediction would imply no scaling (i.e. scaling correction = 1) and no translation (translation correction = 0). The mean translation error for ARMS flow was 6.52 pixels per event vs 8.70 pixels per event for EDL flow. More importantly the scaling error in ARMS was only 0.085 compared to 0.141 in case of EDL. These results show that our proposed ARMS flow reduces the translation error and requires almost no scaling corrections showing that this flow can be used successfully to perform predictions on moving rigid objects.

Real world scenario
We placed the ATIS on a street corner and recorded pedestrians passing by. As in the previous case, for every event, we make prediction on where the event will occur after 500msec using the optical flow computed with local plane fitting or the rectification algorithm. We performed the transformation estimation for clusters of 50msec windows. While the direction component of the flow for each event is used as it is, the speed component of the flow is normalized by the mean speed i.e., each event i in the event-cluster has speed M and direction θ i , where M is the mean speed of all events and θ i is individual flow directions. Using these predictions, a reconstruction of the motion is made based on local and corrected flow as shown in figure 6 by red and blue dots respectively. The figure shows that the ARMS flow can predict the position of the man upto next 500msec very accurately. This is equivalent to about 20 frames from a traditional 25 fps camera. We used the transformation metric as used in the previous experiment to compare the performance of the two methods. The graphs show that the ARMS method outperforms the EDL through the sequence of recording for both scaling and translation corrections. The mean translation error for EDL was 7.1240 pixels while that for ARMS was 4.7558 pixels while the scaling error was 0.297 and 0.167 for EDL and ARMS respectively. Qualitatively, the cluster formed by the predictions based on the ARMS-Flow is less noisy and more compact and is much closer to the real events. This shows that our algorithm can maintain the shape on a rigid moving object even when the predictions are made on an event by event basis and therefore at very high temporal rates. The images shows the actual events (green), predicted events using EDL (red) and predicted events using ARMS (blue) over grayscale images obtained from ATIS. The predictions from ARMS clearly show much better fit with the actual events while the predictions from EDL tend to create inflated shapes. This is quantified in the graphs showing the transformation required to fit the predicted events to the true events. The EDL required larger corrections in both scaling and translation compared to ARMS predictions.

Conclusion
Event driven sensors provide an efficient sampling method to solve computer vision problems with scope for developing novel algorithms in temporal domain. Optical flow is an important feature for most vision based open problems and estimating fast yet robust flow is a crucial step. While some interesting algorithms have been developed to estimate visual flow using the event-driven sensors, they either fail to solve the aperture problem due to the emphasis on local spatio-temporal computation or are inefficient and do not really use the high event speeds of these sensors. In this paper, we have presented a novel visual flow algorithm that not only solves the aperture problem but also performs on an eventby-event basis justifying the use of event-driven sensors. In fact, we exploit the intrinsic property of the event based optical flow algorithm, that allows for correcting the directions of erroneous local flow estimates. We have shown here that the algorithm works in real world scenarios, in case of both stationary and moving camera. The algorithm is invari-ant to the number of objects or their size and does not require additional processing steps such as object detection and tracking. This fast implementation allows us to perform truly event based prediction of moving objects from 250 to 500 msec in future without affecting the shape and size of the object. This is equivalent to around 10-25 frames in traditional frame-based cameras. To the best of our knowledge , we could not find any methods using event-driven sensors that have attempted to perform such accurate predictions without any temporal binning of events. Further these predictions are invariant to the size and number of independent objects in the scene. These predictions can allow higher order recognition and tracking layers to perform at the high temporal rates at which events are generated. Indeed, our future goals are to use this algorithm as part of an autonomous driving car sensor system to allow for fast collision detection and detect abnormal driver and pedestrian behavior. Our algorithm does have certain short comings, as it only corrects the direction of individual flow but does not perfectly correct the magnitude of the flow. An im-D R A F T proved prediction of the magnitude of flow could allow us to make predictions at even longer durations of upto a few seconds. A possible solution to improve the magnitude estimates could be by using the gray scale information provided by the ATIS. A new algorithm to use this information is currently being developed by the authors. Regarding the memory and computation aspects, we implemented the algorithm in C++ on a traditional computer such that it requires very small amount of memory that only increases linearly with respect to the number of pixels in the sensor. While the traditional CPU is good for a QVGA sensor, a parallel neuromorphic hardware implementation could make the algorithm independent of the sensor resolution and allow real time motion based visual processing.