[0001] This application claims priority to U.S. Provisional Application Serial Nos. 62/414,288, 62/418,442, and 62/422,086, filed on October 28, 2016, November 7, 2016, and November 15, 2016 respectively, each of which is incorporated herein by reference herein its entirety.

BACKGROUND

Technical Field

[0002] The present invention relates to scene prediction and, more particularly, to the prediction of future events within a dynamic scene.

Description of the Related Art

[0003] The analysis of dynamic scenes (e.g., video feeds from security cameras or other changing scenes) may identify agents (such as, e.g., people or vehicles) and track their motion through the scene. The scene may include other elements (e.g., roads and crosswalks). Thus, in the example of monitoring a traffic scene, agents may be tracked across the scene elements.

SUMMARY

[0004] A method for predicting a trajectory includes determining prediction samples for agents in a scene based on a past trajectory. The prediction samples are ranked according to a likelihood score that incorporates interactions between agents and semantic scene context. The prediction samples are iteratively refined using a regression function that accumulates scene context and agent interactions across iterations. A response activity is triggered when the prediction samples satisfy a predetermined condition.

[0005] A system for predicting a trajectory includes a prediction sample module configured to determine prediction samples for agents in a scene based on a past trajectory. A ranking/refinement module includes a processor configured to rank the prediction samples according to a likelihood score that incorporates interactions between agents and semantic scene context and to iteratively refine the prediction samples using a regression function that accumulates scene context and agent interactions across iterations. A response module is configured to trigger a response activity when the prediction samples satisfy a predetermined condition.

[0006] These and other features and advantages will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.

BRIEF DESCRIPTION OF DRAWINGS

[0007] The disclosure will provide details in the following description of preferred embodiments with reference to the following figures wherein:

[0008] FIG. 1 is a drawing illustrating a set of past trajectories and a set of predicted trajectories for agents on a background in accordance with an embodiment of the present invention;

[0009] FIG. 2 is a block/flow diagram of a method of prediction generation and refinement in accordance with an embodiment of the present invention; [0010] FIG. 3 is a block/flow diagram of a method of generating trajectory prediction samples in accordance with an embodiment of the present invention;

[0011] FIG. 4 is a block diagram of a system for generating trajectory prediction samples in accordance with an embodiment of the present invention;

[0012] FIG. 5 is a block diagram of a system for predicting future trajectories based on measured past trajectories in accordance with an embodiment of the present invention; and [0013] FIG. 6 is a block diagram of a processing system in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

[0014] Embodiments of the present principles predict behavior of agents in a dynamic scene. In particular, the present embodiments predict the locations of agents and the evolution of scene elements at future times using observations of the past states of the scene, for example in the form of agent trajectories and scene context derived from image- based features or other sensory date (if available).

[0015] The present embodiments thus adapt decision-making to make determinations about object and scene element types using image features. This stands in contrast to sensors like radar, which cannot generally resolve such features. The present embodiments furthermore handle the complex interactions between agents and scene elements in a scalable manner and account for the changes in behavior undertaken by agents in response to, or in anticipation of, the behavior of other agents.

[0016] To this end, the present embodiments formulate the prediction as an optimization that maximizes the potential future reward of the prediction. Because it is challenging to directly optimize the prediction, the present embodiments generate a diverse set of hypothetical predictions and ranks and refines those hypothetical predictions in an iterative fashion.

[0017] Referring now to FIG. 1, an exemplary scene 100 is shown. The scene 100 depicts an intersection that is being monitored and includes a number of agents 102, which in this case may include both pedestrians and automobiles. The past positions of each agent are shown as dotted-line paths 104. Predictions as to an agent's future position are shown as solid lines 106, with thicker lines representing predictions having a higher likelihood and thinner lines representing predictions having a lower likelihood. The scene 100 may be built across many individual images, with agent positions being tracked from image to image. Semantic elements such as, e.g., the crosswalk 108 may also be present and may include such features as lane markings, traffic lights, and road signs. These elements provide semantic scene context that is used to help determine likely agent trajectories.

[0018] Thus, the present embodiments provide the ability to predict behavior in monitored scenes, aiding in early warning of dangerous or criminal activities, predicting dangerous conditions, providing steering information for autonomous vehicles, etc. It should be understood that, although the present embodiments are described in the context of the specific application of traffic scene analysis, these embodiments may be applied to any future-prediction task. The present embodiments provide scalability (because deep learning enables end-to-end training and easy incorporation with multiple cues from past motion, scene context, and agent interactions), diversity (the stochastic output is combined with an encoding of past observations to generate multiple prediction hypotheses that resolve the ambiguities and multimodalities of future prediction), and accuracy (long-term future rewards are accumulated for sampled trajectories and a deformation of the trajectory is learned to provide accurate predictions farther into the future).

[0019] Referring now to FIG. 2, a method for trajectory prediction is shown. Since there can be multiple plausible futures given the same inputs (including images / and past trajectories X), block 202 generates a diverse set of prediction samples Ϋ to provide accurate prediction of future trajectories 106. Toward this end, block 202 employs a conditional variational auto-encoder (CVAE) framework to learn the sampling model. CVAE introduces a latent variable z that accounts for ambiguity in predictions of the future. A recurrent neural network (RNN) is used to produce an encoding h from the inputs that, with z, is passed to another RNN that generates the future prediction samples.

[0020] RNNs are generalizations of feedforward neural networks to sequences. The power of RNNs for sequence-to- sequence modeling makes them useful to the generation of sequential future prediction outputs. The RNNs discussed herein use gated recurrent units (GRUs) over long short-term memory (LSTM) units, since the former is simple but yield no degradation in performance. Contrary to existing RNN models, the present embodiments can predict trajectories of variable length.

[0021] Block 204 then determines the random prediction samples that are most likely to reflect future trajectories while incorporating scene context and interactions. Block 204 ranks the samples and refines them to incorporate contextual and interaction cues. Block 204 uses an RNN that is augmented with a fusion layer that incorporates interaction between agents and a convolutional neural network (CNN) that provides scene information. Block 204 uses training in a multi-task learning framework where the ranking objective is formulated using inverse optimal control (IOC) and the refinement objective is obtained by regression. In a testing phase, the ranking/refinement of block 204 is iterated to obtain more accurate refinements of the prediction of future trajectories.

[0022] Referring now to FIG. 3, additional detail is provided regarding the generation of prediction samples in block 202. In particular, block 302 conducts a training phase, while block 304 conducts a testing phase. The training phase of block 302 uses a set of known past trajectories for n agents, X = {X ₁ , X ₂ , ... , X _n }, and a set of known future trajectories for the n agents, Y = {Y^ Y ₂ , ... , Y _n }, from a set of training data and a set of sensory inputs (e.g., images from a video), 0. The future trajectory of an agent i is thus denoted as Y^ = {yi _, t+i _> Ύίχ+2>■■■ _> ϊίχ+δ} _> with t representing a present time and δ representing a limit to the amount of time into the future into which the prediction extends. The past trajectory for the agent i is similarly denoted as X _t = x _{i t} _ _l+1 , x _{i t} _ _l+2 , ... , with ί representing a limit to the amount of time into the past into which a recorded trajectory extends. The terms x _{i t} and y _iit each represent two-dimensional coordinates for position of the agent i within an image 0 _t captured at time t.

[0023] Future prediction is inherently ambiguous, with uncertainties as to which of several plausible scenarios will result from a given trajectory. Following the example of FIG. 1, a vehicle may make any of a variety of turns at an intersection. As a result, learning a deterministic function /that directly maps {X, 0} to Y will under-represent the potential prediction space and can easily over-fit to training data. Furthermore, a naively trained network with a simple loss will product outcomes that average out all possible outcomes.

[0024] The present embodiments therefore create a deep generative model (CVAE). CVAE can learn the distribution P(Yi conditioned on the input trajectories X _t by introducing a stochastic latent variable z^. CVAE uses multiple neural networks, including a recognition network ()φ (ζι \ Υι, Χι), a prior network Ρ _ν (ζ _ί | _ί ), and a generation network Pg (Yi z ), where θ, <p, and v denote parameters of each network.

[0025] The prior of the latent variables z^ is modulated by the input X^, but this can be relaxed to make the latent variables statistically independent of the input variables such that, e.g., Ρ _ν (ζ.ι \Χ ) = P _v (zi) . CVAE essentially introduces stochastic latent variables z^ that are learned to encode a diverse set of predictions Yi given the input X _t , making it suitable for modeling the one-to-many mapping of predicting future trajectories.

[0026] During training, block 302 learns (z^ | Y _it Xi) such that the recognition network gives higher probability to values of z^ that are likely to produce a reconstruction Y^ that is close to actual predictions given the full context of training data for a given X^ and Y^ . At test time, block 304 samples z^ randomly from the prior distribution and decodes the latent variables through a decoder network to form a prediction hypothesis. This provides a probabilistic inference which serves to handle multi-modalities in the prediction space.

[0027] Block 302 encodes the training data, including a past trajectory X _t and a future Yi for an agent i using respective RNNs with separate sets of parameters. Encoding the training data converts the image to a vector representation. The resulting encodings, J-C _x . and J-C _Y . are concatenated and processed by a fully connected neural network layer with a non-linear activation. Two side-by-side, fully connected layers are followed to produce both the mean μ _ζ . and the standard deviation σ _ζ over∑i . The distribution of z^ is modeled as a Gaussian distribution (e.g., Ζι~(2φ (ζι \Χι, Y _t ) = JV (μ _ζ ., σ _ζ .)) and is regularized by the Kullback-Leibler divergence against a prior distribution P _v (zi) = JV(0, /), where / is the identity matrix and JV(0, /) is a normal distribution with zero mean and unit variance, during training. The fully connected layers convert the set of convolutional feature maps to a vector representation, allowing the network to reason over the entire image, rather than a local receptive field used by the convolutional layers.

[0028] Upon successful training, the target distribution is learned in the latent variable Z _j , which provides random samples from a Gaussian distribution for the reconstruction of Yi in block 304. Since back-propagation is not possible through random sampling, reparameterization is used to make the model differentiable.

[0029] To model Pg ( _i | _i , z _i ), z^ is combined with X _t as follows. The sampled latent variable z^ is passed to one fully connected layer to match the dimension of J-C _x . that is followed by a softmax layer, producing ?( ^z i) - The softmaxed latent variable β(∑ι) is combined with the encodings of past trajectories J-C _x . through a masking operation such as element-wise multiplication. This can be interpreted as a guided drop out, where the guidance β is derived from the full context of individual trajectories during the training phase, while it is randomly drawn from an X _t - and Fj-agnostic distribution in the testing phase of block 304. An RNN decoder takes the output of the previous step, J-C _x . | 1 β(ζι), and generates K future prediction samples for each agent i:

[0030] There are two loss terms in training the CVAR-based RNN encoder/decoder in block 302. A reconstruction loss is defined as ^R _ECON =—∑;<: Y-— Y- (if) The reconstruction loss measures how far the generated samples are from the actual ground truth. A Kullback-Leibler divergence loss is defined as ^KLD ⁼

D _KL (Q(j) (.Zi \ Yi, X \ The Kullback-Leibler divergence loss measures how close

the sampling distribution at test-time is to the distribution of the latent variable learned during training (e.g., approximate inference). [0031] At test time, block 304 does not have access to encodings of future trajectories, so the encodings of past trajectories -C _x ., drawn from recent data, are combined with multiple random samples of latent variable z^ drawn from the prior P _v (zi) . As in the training phase, J-C _x . | 1 ?( ^z i) is passed to the following RNN decoder to generate a diverse set of prediction hypotheses. For both of blocks 302 and 04, trajectories pass through a temporal convolution layer before encoding to encourage the network to learn the concept of velocity from adjacent frames before getting passed into RNN encoders. RNNs are implemented using, e.g., gate recurrent units to learn long-term dependencies, but they can be replaced with any appropriate RNN, such as long short-term memory units.

[0032] Referring now to FIG. 4, a system-oriented view of prediction sample generation block 202 is shown. First RNN encoder 402 and second RNN encoder 404 accept inputs of X and Y respectively. The encoded inputs are then concatenated at block 404, with the concatenated input being sent to two fully connected networks. A first fully connected network 406 determines the mean, while the second fully connected network 408 determines the standard deviation. These two quantities are then used to determine the latent variable z^ .

[0033] Block 412 performs a softmax operation on the latent variable which is then combined with the encoded X input with the | 1 operation at block 414. An RNN decoder 416 then decodes the output of block 414 to produce a predicted future trajectory Y.

[0034] Predicting a distant future trajectory can be significantly more challenging than predicting a trajectory into the near future. Reinforcement learning, where an agent is trained to choose its actions to maximize long-term rewards to achieve a goal, is used to help determine likelier trajectories. The present embodiments learn an unknown reward function with an RNN model that assigns rewards to each prediction hypothesis Y _t and attaches a score based on the accumulated long-term rewards. Block 204 further refines the prediction hypotheses by learning displacements AY _t to the actual prediction through a fully connected layer.

[0035] Block 204 receives iterative feedback from regressed predictions and makes adjustments to produce increasingly accurate predictions. During the iterative refinement, past motion history through the embedding vector J-C _x , semantic scene context through a CNN with parameters p, and interaction among multiple agents using interaction features are combined.

[0036] The score s of an individual prediction hypothesis Y^ for an agent i on a k ^th sample is defined as:

where Y^ _£ is the prediction samples of agents other than agent /, is the k ^th prediction sample of an agent i at time t, is the prediction samples before a time-step t, T is, the maximum prediction length, and ψ(·) is a reward function that assigns a reward value at each time-step. The reward function ψ(·) may be implemented as a fully connected layer that is connected to the hidden vector at t of the RNN module.

[0037] The parameters of the fully connected layer are shared over all the time steps, such that the score s includes accumulated rewards over time, accounting for the entire future rewards being assigned to each hypothesis. The reward function ψ(·) includes both scene context 0 as well as the interaction between agents through the past trajectories. [0038] Block 204 estimates a regression vector AY _t that refines each prediction sample

~ (k)

Y _j . The regression vector for each agent lis obtained with a regression function η defined as follows:

A?W = _J? (f _i ^(fc) ; J, X, Y/

[0039] Represented as parameters of a neural network, the regression function η accumulates both scene contexts and all other agent dynamics from the past to entire future frames and estimates the best displacement vector AY _t over the entire time horizon T. Similar to the score s, it accounts for what happens in the future both in terms of scene context and interactions among dynamic agents to produce an output. The regression function η is implemented as a fully connected layer that is connected to the last hidden vector of the RNN, which outputs an MxT dimensional vector, with M = 2 being the dimension of the location state.

[0040] There are two loss terms in ranking and refinement block 204: a cross-entropy loss and a regression loss. The cross-entropy loss is expressed as _CE = H(p, q), where a target distribution q is obtained by softmax

max Y^— Yi . The regression loss is expressed as £ _Reg = ~∑,k Yi ^{~ ~} Ϋ^ ^ . The total loss of the entire network is defined as a multi-task loss: ⁼ ^∑£ ^Recom + ^KLD + ^ CE + ^Reg ^ where N is the total number of agents in a batch. [0041] Referring now to FIG. 5, a system-oriented view of prediction sample generation block 204 is shown. The prediction samples 501 generated by block 202 are provided as input to a feature pooling block 502 and to an RNN decoder 506. A CNN 504 also takes raw input (before processing by the sample generation of block 202) for semantic scene context processing, providing its output to feature pooling block 502, which combines local entries of a feature map into a more compact representation, allowing the feature map to be invariant to local transformations and/or aggregate information over wider spatial regions. The CNN 504 takes the raw image input and produces semantic segmentation output, where each pixel in the image is labeled by its category (e.g., "sky," "road," "building," "pedestrian," "car," etc.). This makes it possible to incorporate semantic scene information into predictions.

[0042] The feature pooling block 502 provides its output to the RNN decoder 506, which processes the feature pooling output and the prediction samples, providing its output to scoring block 508, which scores the samples and tracks accumulated rewards, and to regression block 510, which provides the regression vector AY _t as feedback that is combined with input 501 for the next iteration.

[0043] The RNN decoder 506 in the ranking and refinement block 204 makes use of information about the past motion context of individual agents, the semantic scene context, and the interaction between multiple agents to provide hidden representations that can score and refine the prediction Y _t . The RNN decoder 506 therefore takes as input: xt = [y ( t> v ( t, ^m pO)) > r (y t ⁾ yj\ _t , ^h ? _t )]

where y _{i t} is a velocity of Y^ at a time t, γ is a fully connected layer with an activation that maps the velocity to a high-dimensional representation space, p ($ΐ ) C ) is a pooling operation that pools the CNN feature p(J) at the location _{i t} , and r (y?i ,' i ^{s an} interaction feature computed by a fusion layer that spatially

aggregates other agents' hidden vectors. The embedding vector J-C _x . (output by the first RNN encoder 402 in the sample generation block 202) is shared as the initial hidden state of the RNN decoder 506 of the ranking and refinement block 204 to provide individual past motion context. This embedding is shared since both involve embedding the same information in the vector.

[0044] The feature pooling block 502 implements a spatial grid. For each sample k of an agent i at time t, spatial grid cells are defined centered at y f . Over each grid cell g, the hidden representation of all the other agents' samples that are within the spatial cell are pooled, Vj≠ i, Vk, y f E g. Average pooling and a log-polar grid may be used to define the spatial grid.

[0045] Embodiments described herein may be entirely hardware, entirely software or including both hardware and software elements. In a preferred embodiment, the present invention is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc.

[0046] Embodiments may include a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system. A computer-usable or computer readable medium may include any apparatus that stores, communicates, propagates, or transports the program for use by or in connection with the instruction execution system, apparatus, or device. The medium can be magnetic, optical, electronic, electromagnetic, infrared, or semiconductor system (or apparatus or device) or a propagation medium. The medium may include a computer-readable storage medium such as a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk and an optical disk, etc.

[0047] Each computer program may be tangibly stored in a machine-readable storage media or device (e.g., program memory or magnetic disk) readable by a general or special purpose programmable computer, for configuring and controlling operation of a computer when the storage media or device is read by the computer to perform the procedures described herein. The inventive system may also be considered to be embodied in a computer-readable storage medium, configured with a computer program, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions described herein.

[0048] A data processing system suitable for storing and/or executing program code may include at least one processor coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code to reduce the number of times code is retrieved from bulk storage during execution. Input/output or I/O devices (including but not limited to keyboards, displays, pointing devices, etc.) may be coupled to the system either directly or through intervening I/O controllers.

[0049] Network adapters may also be coupled to the system to enable the data processing system to become coupled to other data processing systems or remote printers or storage devices through intervening private or public networks. Modems, cable modem and Ethernet cards are just a few of the currently available types of network adapters. [0050] Referring now to FIG. 6, an exemplary processing system 600 is shown which may represent the prediction sample generating system 202 and/or the sample ranking and refinement system 204. The processing system 600 includes at least one processor (CPU) 604 operatively coupled to other components via a system bus 602. A cache 606, a Read Only Memory (ROM) 608, a Random Access Memory (RAM) 610, an input/output (I/O) adapter 620, a sound adapter 630, a network adapter 640, a user interface adapter 650, and a display adapter 660, are operatively coupled to the system bus 602.

[0051] A first storage device 622 and a second storage device 624 are operatively coupled to system bus 602 by the I/O adapter 620. The storage devices 622 and 624 can be any of a disk storage device (e.g., a magnetic or optical disk storage device), a solid state magnetic device, and so forth. The storage devices 622 and 624 can be the same type of storage device or different types of storage devices.

[0052] A speaker 632 is operatively coupled to system bus 602 by the sound adapter 630. A transceiver 642 is operatively coupled to system bus 602 by network adapter 640. A display device 662 is operatively coupled to system bus 602 by display adapter 660.

[0053] A first user input device 652, a second user input device 654, and a third user input device 656 are operatively coupled to system bus 602 by user interface adapter 650. The user input devices 652, 654, and 656 can be any of a keyboard, a mouse, a keypad, an image capture device, a motion sensing device, a microphone, a device incorporating the functionality of at least two of the preceding devices, and so forth. Of course, other types of input devices can also be used, while maintaining the spirit of the present principles. The user input devices 652, 654, and 656 can be the same type of user input device or different types of user input devices. The user input devices 652, 654, and 656 are used to input and output information to and from system 600.

[0054] Of course, the processing system 600 may also include other elements (not shown), as readily contemplated by one of skill in the art, as well as omit certain elements. For example, various other input devices and/or output devices can be included in processing system 600, depending upon the particular implementation of the same, as readily understood by one of ordinary skill in the art. For example, various types of wireless and/or wired input and/or output devices can be used. Moreover, additional processors, controllers, memories, and so forth, in various configurations can also be utilized as readily appreciated by one of ordinary skill in the art. These and other variations of the processing system 600 are readily contemplated by one of ordinary skill in the art given the teachings of the present principles provided herein.

[0055] Referring now to FIG. 7, a video analysis system 700 is shown. The system 700 includes a hardware processor 702 and memory 704. A sensor interface 706 collects data from one or more sensors (e.g., video feeds from cameras or any other appropriate sensor type) and stores the data in memory 704. The system 700 furthermore includes one or more functional modules that, in some embodiments, may be implemented as software that is stored in memory 704 or, in other embodiments, may be implemented as one or more discrete hardware components in the form of, e.g., application specific integrated chips or field programmable gate arrays.

[0056] A training module 708 provides training for neural networks in prediction sample module 710 according to a set of input data that may be stored in the memory 704. The training module 708 uses previous examples of agent trajectories, using the known future trajectories from a particular point in time to train predictions based on a past trajectory. After training, the prediction sample module 710 generates sets of such predictions for the ranking/refinement module 712 to work with, ultimately producing one or more predictions that represent the most likely future trajectories for agents, taking into account the presence and likely actions of other agents in the scene.

[0057] A user interface 714 is implemented to provide a display that shows the future trajectories as an overlay of a most recent piece of sensor data, for example overlaying the most likely trajectory of agents in the field of view of a camera. A response module 716 provides manual or automated actions responsive to the determined trajectories, where a human operator can trigger a response through the user interface 714 or a response can be triggered automatically in response to the trajectories matching certain conditions. For example, a large number of agents being detected at a crosswalk, with likely trajectories of crossing the street, may trigger a change in a lighting system's pattern to provide a "walk" signal to those agents. In another embodiment, the response module 716 may recognize that an agent is likely to enter an area that is dangerous or off- limits, and the response module 716 may then raise an alarm or trigger a barrier to the user's progress (e.g., by locking a door).

[0058] The foregoing is to be understood as being in every respect illustrative and exemplary, but not restrictive, and the scope of the invention disclosed herein is not to be determined from the Detailed Description, but rather from the claims as interpreted according to the full breadth permitted by the patent laws. It is to be understood that the embodiments shown and described herein are only illustrative of the principles of the present invention and that those skilled in the art may implement various modifications without departing from the scope and spirit of the invention. Those skilled in the art could implement various other feature combinations without departing from the scope and spirit of the invention. Having thus described aspects of the invention, with the details and particularity required by the patent laws, what is claimed and desired protected by Letters Patent is set forth in the appended claims.