Methods and Systems for Predicting Flow of Crowds from Limited Observations

• US 20180197017A1
• Filed: 01/12/2017
• Published: 07/12/2018
• Est. Priority Date: 01/12/2017
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Mansour, Hassan, Benosman, Mouhacine, Huroyan, Vahan
• Granted Patent: US 10,210,398 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20081 Training; Learning
• CPC Class Codes: G06T 2207/30241 Trajectory
• CPC Class Codes: G06T 7/215 Motion-based segmentation
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 20/53 Recognition of crowd images, e.g. recognition of crowd congestion

Abstract

Systems and methods for determining flows by acquiring a video of the flows with a camera, wherein the flows are pedestrians in a scene. The video includes a set of frames, wherein motion vectors are extracted from each frame in the set, and a data matrix is constructed from the motion vectors in the set of frames. A low rank Koopman operator can be determined from the data matrix and a spectrum of the low rank Koopman operator can be analyzed to determine a set of Koopman modes. Then, the frames are segmented into independent flows according to a clustering of the Koopman modes.

Claims

1. A system for determining states of flow of objects in a scene, comprising:

at least one sensor to measure the states of the flow at observed sample points of the scene, wherein the scene contains a set of sample points having subsets of observed and unobserved sample points;

a memory to store an operator specifying time-varying dynamics of training states of flow of the objects in the scene, wherein the operator is trained to determine an estimated future state of the states of flow of the objects at a sample point in the scene, as a function of current measured states of the states of flow of the objects at the set of sample points in the scene;

a processor in communication with the memory, configured to estimate, using the operator and the measured states at the subset of observed sample points, the states of the flow of the objects at the subset of unobserved sample points of the scene, such that the estimated future states at the subset of observed sample points are consistent with the measured states at the subset of observed sample points; and

an output interface in communication with the processor, configured for outputting the states of the flow at the set of unobserved sample points of the scene, so as to assist in a management of managing states of flow of objects in the scene.

2. The system of claim 1, wherein the training of the operator includes one or a combination of:

obtaining historical data of training states of the flow of objects in the set of sample points in the scene;

simulating according to a model, the training states of the flow of objects in the set of sample points in the scene;

or

obtaining the training states of the flow of objects in a series of subsets of sample points in the scene,

wherein at least one subset of the sample points in the series of subsets of sample points, are observed sample points at a time that is different than observable sample points times for the remaining subsets of the sample points in the series of subsets of sample points in the scene, such that all the subsets of the sample points in the series of sample points in the scene include all the sample points in the set of sample points in the scene.

3. The system of claim 1, wherein the objects include one or a combination of an animal, a machine, a fluid, a material or an electrical current.

4. The system of claim 1, wherein the states of flow of the object includes one or a combination of a density, a velocity or a flowrate.

5. The system of claim 1, wherein the states of flow of the object includes one or a combination of an electrical current, a voltage, a power or a load.

6. The system of claim 1, wherein the states of flow of the object includes one or a combination of a temperature, a velocity or a density.

7. The system of claim 1, wherein the estimating of the states of the flow of the objects at the subset of unobserved sample points of the scene includes:

determining a set of coefficients for a set of basis matrices by minimizing an error between the set of observed sample points of the scene by the sensors and the estimated future states at the subset of observed sample points of the operator; and

confirming that the set of coefficients for the set of basis matrices conform to a temporal prediction condition according to a set of eigenvalues of the operator.

8. The system of claim 7, further comprising:

minimizing an error between subsets of coefficients of the set of coefficients for the set of basis matrices that are associated with correlating the set of observed sample points of the scene by the sensors and the estimated states at the subset of observed sample points of the operator.

9. The system of claim 1, wherein the estimating of the states of the flow of the objects at the subset of unobserved sample points of the scene includes:

determining a dynamical system, wherein the dynamical system includes an observer, such the observer includes an observer model.

10. The system of claim 9, wherein the operator includes a set of operator modes and a set of eigenvalues.

11. The system of claim 10, wherein the estimating of the states of the flow of the objects at the subset of unobserved sample points of the scene is according to the observer model, and includes:

determining, based on the set of operator modes of the operator, a set of complete modes for the states of the flow of the objects at all sample points in the set of sample points of the scene;

determining a subset of observable modes of the set of operator modes for the states of the flow of the objects at the subset of the observed sample points of the scene;

determining a stabilizing feedback gain for an observer model of the flow of the objects at the subset of the observed sample points of the scene by assigning pole eigenvalues of the feedback gain inside a complex unit circle;

estimating a set of basis functions by confirming that the multiplication of the set of basis functions with the set of the observable modes conform to a temporal prediction condition according to the set of eigenvalues of the operator;

generating the states of flow of the objects at the subset of the unobserved sample points by multiplying the set of complete modes by the set of basis functions; and

outputting the states of the flow at the set of unobserved sample points of the scene.

12. The system of claim 1, wherein the at least one sensor is a camera capturing video of the flows of objects, and the flow of objects are pedestrians in the scene, such that the video includes a set of frames, such that the flows are independent pedestrian flows obtained from each frame in the set of frames in the subset of the observed sample points of the scene, and the subset of the observed sample points of the scene are selected from a group consisting of a set of velocity vectors, a set of crowd densities, a set of optical flow vectors or a set of motion vectors.

13. The system of claim 1, wherein the operator specifying time-varying dynamics of training states of flow of the objects at the set of sample points in the scene is selected from a group consisting of a Koopman operator, a dynamic mode decomposition operator, an extended dynamic mode decomposition operator and a kernel dynamic mode decomposition operator.

14. The system of claim 1, wherein the measured states at the subset of observed sample points include noise observations, such that the estimated future states at the subset of observed sample points are consistent or equal to the measured states less the noise observations at the subset of observed sample points.

15. A method for determining states of flow of objects in a scene, comprising:

acquiring measured states of the flow at observed sample points of the scene generated by at least one sensor, wherein the scene contains a set of sample points having subsets of observed and unobserved sample points;

using a memory having stored thereon an operator specifying time-varying dynamics of training states of flow of the objects in the scene, wherein the operator is trained to determine an estimated future state of the states of flow of the objects at a sample point in the scene, as a function of current measured states of the states of flow of the objects at the set of sample points in the scene;

estimating, by a processor in communication with the memory, and using the operator and the measured states at the subset of observed sample points, the states of the flow of the objects at the subset of unobserved sample points of the scene, such that the estimated future states at the subset of observed sample points are consistent with the measured states at the subset of observed sample points; and

outputting, via an output interface in communication with the processor, the states of the flow at the set of unobserved sample points of the scene, so as to assist in a management of managing states of flow of objects in the scene.

16. The method of claim 15, wherein the training of the operator includes one or a combination of:

obtaining historical data of training states of the flow of objects in the set of sample points in the scene;

simulating according to a model, the training states of the flow of objects in the set of sample points in the scene;

or

obtaining the training states of the flow of objects in a series of subsets of sample points in the scene,

wherein at least one subset of the sample points in the series of subsets of sample points, are observed sample points at a time that is different than observable sample points times for the remaining subsets of the sample points in the series of subsets of sample points in the scene, such that all the subsets of the sample points in the series of sample points in the scene include all the sample points in the set of sample points in the scene.

17. The method of claim 15, wherein the estimating of the states of the flow of the objects at the subset of unobserved sample points of the scene includes:

determining a set of coefficients for a set of basis matrices by minimizing an error between the set of observed sample points of the scene by the sensors and the estimated future states at the subset of observed sample points of the operator;

confirming that the set of coefficients for the set of basis matrices conform to a temporal prediction condition according to a set of eigenvalues of the operator; and

minimizing an error between subsets of coefficients of the set of coefficients for the set of basis matrices that are associated with correlating the set of observed sample points of the scene by the sensors and the estimated states at the subset of observed sample points of the operator.

18. A non-transitory computer readable storage medium embodied thereon a program executable by a computer for performing a method, the method for determining states of flow of objects in a scene, the method comprising:

acquiring measured states of the flow at observed sample points of the scene generated by at least one sensor, wherein the scene contains a set of sample points having subsets of observed and unobserved sample points;

using a memory having stored thereon an operator specifying time-varying dynamics of training states of flow of the objects in the scene, wherein the operator is trained to determine an estimated future state of the states of flow of the objects at a sample point in the scene, as a function of current measured states of the states of flow of the objects at the set of sample points in the scene;

estimating, by a processor in communication with the memory, and using the operator and the measured states at the subset of observed sample points, the states of the flow of the objects at the subset of unobserved sample points of the scene, such that the estimated future states at the subset of observed sample points are consistent with the measured states at the subset of observed sample points; and

outputting, via an output interface in communication with the processor, the states of the flow at the set of unobserved sample points of the scene, so as to assist in a management of managing states of flow of objects in the scene.

19. The method of claim 18, wherein the training of the operator includes one or a combination of:

obtaining historical data of training states of the flow of objects in the set of sample points in the scene;

simulating according to a model, the training states of the flow of objects in the set of sample points in the scene;

or

obtaining the training states of the flow of objects in a series of subsets of sample points in the scene,

wherein at least one subset of the sample points in the series of subsets of sample points, are observed sample points at a time that is different than observable sample points times for the remaining subsets of the sample points in the series of subsets of sample points in the scene, such that all the subsets of the sample points in the series of sample points in the scene include all the sample points in the set of sample points in the scene.

20. The method of claim 18, wherein estimating of the states of the flow of the objects at the subset of unobserved sample points of the scene includes:

determining a dynamical system, wherein the dynamical system includes an observer, wherein the observer includes an observer model, such that the operator includes a set of operator modes and a set of eigenvalues;

estimating of the states of the flow of the objects at the subset of unobserved sample points of the scene is according to the observer model, and includes;

determining, based on the set of operator modes of the operator, a set of complete modes for the states of the flow of the objects at all sample points in the set of sample points of the scene;

determining a subset of observable modes of the set of operator modes for the states of the flow of the objects at the subset of the observed sample points of the scene;

determining a stabilizing feedback gain for an observer model of the flow of the objects at the subset of the observed sample points of the scene by assigning pole eigenvalues of the feedback gain inside a complex unit circle;

estimating a set of basis functions by confirming that the multiplication of the set of basis functions with the set of the observable modes conform to a temporal prediction condition according to the set of eigenvalues of the operator;

generating the states of flow of the objects at the subset of the unobserved sample points by multiplying the set of complete modes by the set of basis functions; and

outputting the states of the flow at the set of unobserved sample points of the scene.