Real-time crowd density estimation from video

• US 7,139,409 B2
• Filed: 08/31/2001
• Issued: 11/21/2006
• Est. Priority Date: 09/06/2000
• Status: Active Grant

• Current Assignee: Siemens Corp. (Siemens AG)
• Original Assignee: Siemens Corporate Research Incorporated (Siemens AG)
• Inventors: Ramesh, Visvanathan, Paragios, Nikos, Stenger, Bjoern, Coetzee, Frans
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): LAVIN, CHRISTOPHER L
• Application Number:
  US09/944,317
• Publication Number:
  US 20020122570A1
• Time in Patent Office: 1,908 Days
• Field of Search: 382/103, 356/4.03
• US Class Current: 382/103
• CPC Class Codes: G06T 7/254 involving subtraction of images
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 20/53 Recognition of crowd images, e.g. recognition of crowd congestion

Abstract

A system and method for automated and/or semi-automated analysis of video for discerning patterns of interest in video streams. In a preferred embodiment, the present invention is directed to identifying patterns of interest in indoor settings. In one aspect, the present invention deals with the change detection problem using a Markov Random Field approach where information from different sources are naturally combined with additional constraints to provide the final detection map. A slight modification is made of the regularity term within the MRF model that accounts for real-discontinuities in the observed data. The defined objective function is implemented in a multi-scale framework that decreases the computational cost and the risk of convergence to local minima. To achieve real-time performance, fast deterministic relaxation algorithms are used to perform the minimization. The crowdedness measure used is a geometric measure of occupancy that is quasi-invariant to objects translating on the platform.

Claims

1. A method of video analysis comprising the steps of:

estimating a background reference model comprising of a plurality of states for representing a background;

estimating geometric parameters for representing size changes of objects as the objects are moved at various depths in a given frame, the geometric parameters comprising a weighting for each pixel in the given frame;

providing input video data comprising a plurality of input frames;

obtaining a change detection map for distinguishing the background from the objects in each input frame, based on a Markov Random Field approach wherein a difference between an input frame and a most probable background reference state is analyzed using a statistical model, wherein information regarding expected background properties and normalized color background properties is combined with spatial and neighborhood constraints and temporal differences due to object motion in the context of said MRF using local dependencies to ensure smoothness; and

determining a measure of congestion of the given frame by combining the change detection map with the geometric parameters.

2. The method of claim 1, wherein the step of estimating the background reference model further comprises:

initializing each region of the image with a single node and a local model;

evaluating confidence limits of the local model;

evaluating the local model to determine a multi-modality, wherein if a multi-modality is detected, further comprising;

splitting the local model into multiple nodes.

3. The method of claim 1, wherein said size changes comprises variation in the object'"'"'s width and height as a function of said object'"'"'s position in the given frame.

4. The method of claim 1, further comprising the step of updating the background reference model using the change detection map.

5. The method of claim 1, wherein the measure of congestion is a prolonged temporal event wherein a given percentage of a platform area is crowded with people for a given period of time.

6. The method of claim 2, wherein each of said multiple nodes is assigned to a new state.

7. The method of claim 4, wherein static pixels of the background reference model are updated.

8. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for video analysis comprising the steps of:

estimating a background reference model comprising of a plurality of states for representing a background;

estimating geometric weights for each pixel for representing a scale variation of objects in a given frame;

providing input video data comprising a plurality of input frames;

obtaining a change detection map for distinguishing the background from the objects in each input frame, based on a Markov Random Field approach wherein a difference between an input frame and a most probable background reference state is analyzed using a statistical model, wherein information regarding expected background properties and normalized color background properties is combined with spatial and neighborhood constraints and temporal differences due to object motion in the context of said MRF using local dependencies to ensure smoothness; and

determining a measure of congestion of the given frame by combining the change detection map with the geometric weights.

9. The program storage device of claim 8, wherein the step of estimating the background reference model further comprises:

initializing each region of the image with a single node and a local model;

evaluating confidence limits of the local model;

evaluating the local model to determine a multi-modality, wherein if a multi-modality is detected, further comprising;

splitting the local model into multiple nodes.

10. The program storage device of claim 8, wherein said scale variation comprises variation in the object'"'"'s width and height as a function of said object'"'"'s position in the given frame.

11. The program storage device of claim 8, further comprising the step of updating the background reference model using the change detection map.

12. The program storage device of claim 8, wherein the measure of congestion is a prolonged temporal event wherein a given percentage of a subway platform is crowded for a user-defined period of time.

13. The program storage device of claim 9, wherein each of said multiple nodes is assigned to a new state.

14. The program storage device of claim 11, wherein static pixels of the background reference model are updated.

15. A method of video analysis comprising the steps of:

estimating a background reference model comprising of a plurality of states representing a platform area;

estimating geometric parameters for representing size changes of objects as the objects move at various depths on the platform area in a given frame, the geometric parameters comprising a weighting for each pixel of the people in the given frame;

obtaining a change detection map for distinguishing the background from the objects in the given frame, based on a Markov Random Field approach wherein a difference between the given frame and a most probable background reference state is analyzed using a statistical model, wherein information regarding expected background properties and normalized color background properties is combined with spatial and neighborhood constraints and temporal differences due to object motion in the context of said MRF using local dependencies to ensure smoothness; and

determining a measure of congestion of the platform area by combining the change detection map with the geometric parameters, wherein the measure of congestion comprises a prolonged temporal event wherein a given percentage of the platform area is crowded with the people for a given period of time.

16. The method of claim 15, wherein said change detection map is modeled by a multi-scale grid label model using detection maps constrained to be piecewise constant over smaller subsets.