Dynamic background estimation for video analysis using evolutionary optimization

Patent metadata

Field	Value
Publication number	US-9805301-B1
Application number	US-58351909-A
Country	US
Kind code	B1
Filing date	Aug 20, 2009
Priority date	Mar 4, 2005
Publication date	Oct 31, 2017
Grant date	Oct 31, 2017

Abstract

Described is a system for dynamic background estimation which utilizes Particle Swarm Optimization (PSO). The present invention comprises a system, method, and computer program product for accurate estimation of a background mask corresponding to a dynamically changing scene. The system is configured to construct a background template model of a scene, and then capture an image of a current view of the scene with a camera. Thereafter, the system generates an image-based template matching cost function as an optimization problem, where the objective is to identify and fit a corresponding subregion of the background template model to the current camera view. The cost function is optimized using a PSO search algorithm. Finally, the system is configured to generate the corresponding subregion of the background template model for display. The inherent efficiency of PSO makes this system conducive for use in applications requiring real-time background estimation.

First claim

What is claimed is:

1. A system for background estimation, the system comprising one or more processors that are configured to perform operations of:
constructing and learning a background template model of a field-of view of a scene captured with a camera a priori;
capturing a current image of the scene with the camera, the current image of the scene having a dynamically changing field-of-view of the scene that is smaller than the field-of-view of the background template model;
minimizing a template matching cost function to identify a parameter x* for a parameterized patch of the background template model which corresponds to the camera's current field-of-view, wherein the template matching cost function takes a parameter x as input and outputs a normalized scalar score corresponding to a match between the camera's current field-of-view and the parameterized patch of the background template model using an image similarity measure selected from the group consisting of normalized cross correlation and L2 distances,
wherein the template matching cost function is minimized through utilization of a plurality of particles which operates as a cooperative swarm in sampling the cost function over a search domain of the background template model and iteratively migrates towards the parameter x*;
for each current field-of-view, continuously matching the camera's current field-of-view with the parameterized patch of the background template model;
subtracting the parameterized patch of the background template model from the camera's current field-of-view to extract a foreground mask; and
generating a display of the foreground mask for detecting at least one object of interest within the foreground mask.

2. A system for background estimation as set forth in claim 1 , wherein the cost function to be optimized is J(x)=d(I(x),Io), with J: 2 →[0, 1],
where I o ∈ w×h represents the image corresponding to the current scene, I(x)∈ w×h represents an image corresponding to the parameterized patch of the background template model centered at x∈Ω⊂R 2 having the same dimensions as I o ∈ w×h , where x is an input parameter, d(.) represents an image similarity measure, R denotes the set of real numbers, w is the width of the image, h is the height of the image, ∈ denotes an element of, Ω represents the search domain, and → represents a function arrow.

3. A system for background estimation as set forth in claim 2 , wherein the image similarity measure varies with respect to at least one misalignment between the background template and the current scene.

4. A system for background estimation as set forth in claim 3 , wherein in the act of optimizing the cost function, the plurality of particles begin at a randomly initialized state, where each particle migrates towards the optimal solution in the search domain according to the following:
x i ( t+ 1)= F ( x i ( t ), p best i ( t ), g best( t )),
where x(t) corresponds to a particle i's trajectory, pbest represents a particle's current best solution found up to time t, gbest represents a current global best solution among all particles up to time t, and F(.) represents a particle's dynamic evolution as a function of its current position or state, pbest, and gbest.

5. A computer-implemented method for background estimation, the method comprising an act of causing a processor to perform operations of:
constructing and learning a background template model of a field-of view of a scene captured with a camera a priori;
constructing and learning a background template model of a field-of view of a scene captured with a camera a priori;
capturing a current image of the scene with the camera, the current image of the scene having a dynamically changing field-of-view of the scene that is smaller than the field-of-view of the background template model;
minimizing a template matching cost function to identify a parameter x* for a parameterized patch of the background template model which corresponds to the camera's current field-of-view, wherein the template matching cost function takes a parameter x as input and outputs a normalized scalar score corresponding to a match between the camera's current field-of-view and the parameterized patch of the background template model using an image similarity measure selected from the group consisting of normalized cross correlation and L2 distances,
wherein the template matching cost function is minimized through utilization of a plurality of particles which operates as a cooperative swarm in sampling the cost function over a search domain of the background template model and iteratively migrates towards the parameter x*;
for each current field-of-view, continuously matching the camera's current field-of-view with the parameterized patch of the background template model;
subtracting the parameterized patch of the background template model from the camera's current field-of-view to extract a foreground mask; and
generating a display of the foreground mask for detecting at least one object of interest within the foreground mask.

6. A method for background estimation as set forth in claim 5 , wherein the cost function to be optimized is J(x)=d(I(x),Io), with J: 2 →[0, 1],
where I o ∈ w×h represents the image corresponding to the current scene, I(x)∈ w×h represents an image corresponding to the parameterized patch of the background template model centered at x∈Ω⊂R 2 having the same dimensions as I o ∈ w×h , where x is an input parameter, d(.) represents an image similarity measure, R denotes the set of real numbers, w is the width of the image, h is the height of the image, ∈ denotes an element of, Ω represents the search domain, and → represents a function arrow.

7. A method for background estimation as set forth in claim 6 , wherein the image similarity measure varies with respect to at least one misalignment between the background template and the current scene.

8. A method for background estimation as set forth in claim 7 , wherein in the act of optimizing the cost function, the plurality of particles begin at a randomly initialized state, where each particle migrates towards the optimal solution in the search domain according to the following:
x i ( t+ 1)= F ( x i ( t ), p best i ( t ), g best( t )),
where x(t) corresponds to a particle i's trajectory, pbest represents a particle's current best solution found up to time t, gbest represents a current global best solution among all particles up to time t, and F(.) represents a particle's dynamic evolution as a function of its current position or state, pbest, and gbest.

9. A computer program product for background estimation, the computer program product comprising computer-readable instruction means stored on a non-transitory computer-readable medium that are executable by a computer having a processor for causing the processor to perform operations of:
constructing and learning a background template model of a field-of view of a scene captured with a camera a priori;
capturing a current image of the scene with the camera, the current image of the scene having a dynamically changing field-of-view of the scene that is smaller than the field-of-view of the background template model;
minimizing a template matching cost function to identify a parameter x* for a parameterized patch of the background template model which corresponds to the camera's current field-of-view, wherein the template matching cost function takes a parameter x as input and outputs a normalized scalar score corresponding to a match between the camera's current field-of-view and the parameterized patch of the background template model using an image similarity measure selected from the group consisting of normalized c

Assignees

• Owechko Yuri
• Medasani Swarup
• Saisan Payam
• Hrl Lab Llc

Inventors

• Owechko Yuri
• Medasani Swarup
• Saisan Payam

Classifications

• G06V10/771

  Feature selection, e.g. selecting representative features from a multi-dimensional feature space · CPC title

• G06V40/103 Primary

  Static body considered as a whole, e.g. static pedestrian or occupant recognition · CPC title

• G06N3/006 Primary

  based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO] · CPC title

• G06F18/2111

  by using evolutionary computational techniques, e.g. genetic algorithms · CPC title

• G06V10/25

  Determination of region of interest [ROI] or a volume of interest [VOI] · CPC title