System and method for video-based determination of queue configuration parameters

1. A method for automatically determining a dynamic queue configuration, the method comprising:

a queue dynamics monitoring device acquiring a series of frames from an image source surveying a queue area;

the queue dynamics monitoring device detecting at least one subject in a frame;

the queue dynamics monitoring device tracking locations of each detected subject across the series of frames;

in response to an occupancy in the queue area meeting a predetermined level, the queue dynamics monitoring device clustering sequences of points across the series of frames using the tracking locations of the subjects;

the queue dynamics monitoring device computing a Mahalanobis distance between a centroid of a last trajectory added to each cluster and a select trajectory, wherein the select trajectory is a set of the tracking locations corresponding to one subject, and wherein a covariance estimate is given by a sample covariance of the last trajectory added to the each cluster;

the queue dynamics monitoring device adding the select trajectory to a nearest cluster according to the computed distances;

and

the queue dynamics monitoring device estimating a queue configuration by fitting one of a spline or manifold to the each cluster to identify the queue configuration.

2. The method of claim 1 , wherein the tracking locations of each detected subject includes:

generating spatio-temporal information describing the locations of the each subject in pixel coordinates as a function of time.

3. The method of claim 1 further comprising:

performing a geometric transformation on the tracking data by converting the pixel coordinates to one of real-world coordinates, a coordinate system of a camera in the image source, and a reference coordinate system.

4. The method of claim 3 further comprising:

in response to the tracking data being acquired from at least two image sources, mapping coordinate systems of each individual image source into a common coordinate system.

5. The method of claim 1 further comprising:

classifying an occupancy in the queue area into one of at least two predetermined levels.

6. The method of claim 5 , wherein the classifying includes:

computing a metric corresponding to the queue occupancy;

comparing the metric to a predetermined threshold;

in response to the metric not meeting the threshold, classifying the occupancy in the queue area as belonging to a first predetermined level; and,

in response to the metric meeting and exceeding the threshold, classifying the occupancy in the queue area as belonging to a second predetermined level.

7. The method of claim 6 further comprising:

in response to the occupancy being classified as belonging to the first predetermined level, employing a variable pipeline latency approach to localize the queue configuration descriptor; and,

in response to the occupancy being classified as belonging to the second predetermined level, employing a constant pipeline latency approach to localize the queue configuration descriptor.

8. The method of claim 1 , wherein the estimating the queue configuration descriptor includes:

determining a start point where a queue forms in at least one of the series of frames;

identifying at least one subject located near the start point in a select frame;

backtracking the locations of the at least one subject in the series of frames from the start point; and,

generating a mapping of the locations of the at least one subject across the series of frames; and,

fitting a primitive descriptor to the set of locations generated by the mapping; and

associating the fitted primitive descriptors as the queue configuration descriptor.

9. The method of claim 1 , wherein the estimating the queue configuration descriptor includes:

fitting a primitive descriptor to sets of trajectories belonging to each resulting cluster; and,

associating the fitted primitive descriptors as the queue configuration descriptor.

10. The method of claim 9 , further comprising:

extracting at least one queue-related parameter from the queue configuration descriptor; and,

providing the queue-related parameter as output.

11. A system for automatically determining a dynamic queue configuration, the system comprising a server computer device for monitoring queue dynamics including a memory in communication with a processor operative to:

acquire a series of frames over a network from an image source in communication with the server computer and surveying a queue area;

detect at least one subject in a frame;

track locations of each detected subject across the series of frames; and,

in response to an occupancy in the queue area meeting a predetermined level, clustering sequences of points across the series of frames using the tracking locations of the subjects;

computing a Mahalanobis distance between a centroid of a last trajectory added to each cluster and a select trajectory, wherein the select trajectory is a set of the tracking locations corresponding to one subject, and wherein a covariance estimate is given by a sample covariance of the last trajectory added to the each cluster;

adding the select trajectory to a nearest cluster according to the computed distances; and

estimating a queue configuration by fitting one of a spline or manifold to the each cluster to identify the queue configuration.

12. The system of claim 11 , wherein the processor is further configured to:

generate spatio-temporal information describing the locations of the each subject in pixel coordinates as a function of time.

13. The system of claim 11 , wherein the processor is further configured to:

perform a geometric transformation on the tracking data by converting the pixel coordinates to one of real-world coordinates, a coordinate system of a camera in the image source, and a reference coordinate system.

14. The system of claim 13 , wherein the processor is further configured to:

in response to the tracking data being acquired from at least two image sources, map coordinate systems of each individual image source into a common coordinate system.

15. The system of claim 11 , wherein the processor is further configured to:

classify an occupancy in the queue area into one of at least two predetermined levels.

16. The system of claim 15 , wherein the processor is further configured to:

compute a metric corresponding to the occupancy;

compare the metric to a predetermined threshold;

in response to the metric not meeting the threshold, classify the occupancy in the queue area as belonging to a first predetermined level; and,

in response to the metric meeting and exceeding the threshold, classify the occupancy in the queue area as belonging to a second predetermined level.

17. The system of claim 16 , wherein the processor is further configured to:

in response to the occupancy being classified as belonging to the first predetermined level, employ a pipeline latency approach to localize the queue configuration descriptor; and,

in response to the occupancy being classified as belonging to the second predetermined level, employ a constant pipeline latency approach to localize the queue configuration descriptor.

18. The system of claim 11 , wherein the processor is further configured to:

fit a primitive descriptor to the set of locations generated by the mapping; and

associate the fitted primitive descriptors as the queue configuration descriptor.

19. The system of claim 11 , wherein the processor is further configured to:

track sequences of points across a predetermined number of frames using the tracking data of the each subject to generate a set of trajectories, each trajectory corresponding to a subject;

initialize clusters of trajectories by placing a cluster seed at a location corresponding to each start point where a queue forms;

process at least one trajectory relative to the clusters of trajectories, the trajectory currently unassigned to a cluster, the processing including:

compute a Mahalanobis distance (x i −x j ) T Σ −1 (x i −x j ) between a centroid of a last trajectory added to a cluster, x i and an unassigned candidate trajectory x j , wherein a covariance estimate Σ is given by a sample covariance of the last trajectory added to the candidate cluster,

in response to the computed distance not meeting and exceeding a predetermined threshold, add the trajectory to the cluster to which the trajectory is closest according to the computed distance,

in response to the computed distance meeting and exceeding a predetermined threshold, discard the trajectory, and

repeat the computing until no trajectories remain to be processed;

fit a primitive descriptor to sets of trajectories belonging to each resulting cluster; and,

associate the fitted primitive descriptors as the queue configuration descriptor.

20. The system of claim 11 , wherein the processor is further adapted to:

extract at least one queue-related parameter from the queue configuration descriptor; and,

provide the queue-related parameter as output.