Methods and systems for predicting flow of crowds from limited observations

• US 10,210,398 B2
• Filed: 01/12/2017
• Issued: 02/19/2019
• 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
• Primary Examiner(s): Woldemariam, Aklilu
• Application Number:
  US15/404,296
• Publication Number:
  US 20180197017A1
• Time in Patent Office: 768 Days
• Field of Search: 382103, 382173, 382218, 348144, 348152, 348155, 348135, 348143, 348159, 340439, 340576
• 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, wherein the objects include one or a combination of an animal, a machine, a fluid, a material or an electrical current, the system 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 historical training data including flow of objects in the scene and a non-parametric operator specifying time-varying dynamics of training states of flow of the objects in the scene, wherein the non-parametric operator includes a set of operator eigenvalues and a set of operator modes that determine 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, and wherein the non-parametric 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;

an input interface in communication with the at least one sensor, to acquire the current measured states of the flow of the objects at the observed sample points of the scene;

a processor in communication with the memory and the input interface, configured to estimate, using the non-parametric operator and the current measured states at the subset of observed sample points along with the states of the flow of the objects at the subset of unobserved sample points of the scene, the estimated future states at the subset of observed sample points and at the subset of unobserved sample points, to ascertain 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 non-parametric 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 states of flow of the object includes one or a combination of a density, a velocity, temperature or a flowrate.

4. 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.

5. The system of claim 1, wherein the non-parametric operator is a data dependent operator that directly estimates the states of the flow without requiring parameters to represent motion, such as physical quantities or space.

6. 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 non-parametric 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 non-parametric operator.

7. The system of claim 6, 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 non-parametric operator.

8. 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.

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 is according to the observer model, and includes:

determining, based on the set of operator modes of the non-parametric 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 non-parametric 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.

10. 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.

11. The system of claim 1, wherein the non-parametric 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.

12. 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.

13. A method for determining states of flow of objects in a scene, wherein the objects include one or a combination of an animal, a machine, a fluid, a material or an electrical current, 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 historical training data including flow of objects in the scene and a non-parametric operator specifying time-varying dynamics of training states of flow of the objects in the scene, wherein the non-parametric operator includes a set of operator eigenvalues and a set of operator modes that determine 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, and wherein the non-parametric 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;

acquiring the current measured states of the flow of the objects at the observed sample points of the scene via an input interface in communication with the at least one sensor;

estimating, by a processor in communication with the memory and the input interface, and using the non-parametric operator and the current measured states at the subset of observed sample points along with the states of the flow of the objects at the subset of unobserved sample points of the scene, the estimated future states at the subset of observed sample points and at the subset of unobserved sample points, to ascertain 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.

14. The method of claim 13, wherein the training of the non-parametric 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.

15. The method of claim 13, 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 non-parametric 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 non-parametric 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 non-parametric operator.

16. 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, wherein the objects include one or a combination of an animal, a machine, a fluid, a material or an electrical current, 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 historical training data including flow of objects in the scene and a non-parametric operator specifying time-varying dynamics of training states of flow of the objects in the scene, wherein the non-parametric operator includes a set of operator eigenvalues and a set of operator modes that determine 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, and wherein the non-parametric 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, wherein the non-parametric operator is a data dependent operator that directly estimates the states of the flow without requiring parameters to represent motion;

acquiring the current measured states of the flow of the objects at the observed sample points of the scene via an input interface in communication with the at least one sensor;

estimating, by a processor in communication with the memory and the input interface, and using the non-parametric operator and the current measured states at the subset of observed sample points along with the states of the flow of the objects at the subset of unobserved sample points of the scene, the estimated future states at the subset of observed sample points and at the subset of unobserved sample points, to ascertain 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.

17. The method of claim 16, wherein the training of the non-parametric 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.

18. The method of claim 16, 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 non-parametric operator includes the set of operator modes and the 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 non-parametric 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 non-parametric 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.