VISUAL BACKGROUND EXTRACTOR

• US 20100208998A1
• Filed: 07/16/2008
• Published: 08/19/2010
• Est. Priority Date: 07/08/2007
• Status: Active Grant

• Current Assignee: Université de Liège
• Original Assignee: Université de Liège
• Inventors: Barnich, Olivier, Van Droogenbroeck, Marc
• Granted Patent: US 8,009,918 B2
• Time in Patent Office: Days
• US Class Current: 382/195
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20081 Training; Learning
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06T 7/215 Motion-based segmentation
• 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

Abstract

The present invention relates to a Visual Background Extractor (VIBE) consisting in a method for detecting a background in an image selected from a plurality of related images. Each one of said set of images is formed by a set of pixels, and captured by an imaging device. This background detection method comprising the steps of: establishing, for a determined pixel position in said plurality of images, a background history comprising a plurality of addresses, in such a manner as to have a sample pixel value stored in each address; comparing the pixel value corresponding to said determined pixel position in the selected image with said background history, and, if said pixel value from the selected image substantially matches at least a predetermined number of said sample pixel values: classifying said determined pixel position as belonging to the image background; and—updating said background history by replacing the sample pixel values in one randomly chosen address of said background history with said pixel value from the selected image. The method of the invention is applicable a.o. for video surveillance purposes, videogame interaction and imaging devices with embedded data processors.

Claims

1. A method for detecting a background in an image selected from a plurality of related images, each formed by a set of pixels, and captured by an imaging device, this background detection method comprising the steps of:

establishing, for a determined pixel position in said plurality of images, a background history comprising a plurality of addresses, in such a manner as to have a sample pixel value stored in each address;

comparing the pixel value corresponding to said determined pixel position in the selected image with said background history, and, if said pixel value from the selected image substantially matches at least a predetermined number of sample pixel values of said background history;

classifying said determined pixel position as belonging to the image background; and

updating said background history by replacing one of its sample pixel values with said pixel value from the selected image;

and characterized in that;

the address of the sample pixel value to be replaced is randomly chosen.

2. The method according to claim 1, further comprising a random update selection step, wherein it is randomly determined with a predetermined background history update probability whether said updating step is to be carried out or not.

3. The method according to claim 2, wherein at least one auxiliary history, corresponding to said determined pixel position and also comprising a plurality of addresses, is also established in such a manner as to have a sample pixel value stored in each address, and further comprising the steps, if said pixel value from the selected image does not substantially match at least said predetermined number of sample pixel values of the background history, of:

comparing said pixel value from the selected image with said auxiliary history, and, if it substantially matches at least a further predetermined number of said sample pixel values in said auxiliary history;

randomly determining with an auxiliary history update probability factor higher than the background history update probability factor whether the additional history is to be updated or not; and

, if yes,

updating said auxiliary history by replacing a sample pixel value from a randomly selected address in the auxiliary history with said pixel value from the selected image.

4. The method according to claim 3, which, if said pixel value from the selected image substantially matches at least said further predetermined number of sample pixel values of said auxiliary history, further comprises the steps of:

randomly determining with a predetermined background seeding probability lower than the auxiliary history update probability whether the background history is also to be updated with the pixel value from the selected image; and

, if yes,

updating the background history by replacing a sample pixel value from a randomly selected address in the background history with said pixel value from the selected image.

5. The method according to claim 1, wherein the step of establishing said background history comprises reading pixel values in neighbouring pixel positions in at least one image of said plurality of related images other than said selected image, and storing these pixel values, randomly sorted in the plurality of addresses of said background history, as sample pixel values.

6. The method according to claim 5, wherein said neighbouring pixel positions are randomly chosen within a neighbourhood of the determined pixel position.

7. The method according to claim 1, wherein, if said pixel value in said determined pixel position of said selected image substantially matches at least said predetermined number of sample pixel values in the background history of said determined pixel position, a background history corresponding to a neighbouring pixel, comprising another plurality of addresses, and established in such a manner as to have a sample pixel value stored in each address, is also updated by replacing the sample pixel value in a randomly chosen address in said background history of the neighbouring pixel with the pixel value of the determined pixel position in the selected image.

8. The method according to claim 7, wherein the position of the neighbouring pixel is randomly chosen within a neighbourhood of the determined pixel position.

9. The method according to claim 7, further comprising a random neighbouring pixel history update selection step, wherein it is randomly determined with a predetermined neighbouring pixel background history update probability whether a neighbouring pixel history is to be updated or not.

10. The method according to claim 1, also comprising the steps of:

dividing said selected image into a plurality of sub-sampling areas; and

randomly selecting one such determined pixel position in each sub-sampling area as representative of the whole sub-sampling area.

11. The method according to claim 1, further comprising a step of reallocating a background history of another pixel position to said determined pixel position within said image in response to image motion, such as panning or zooming.

12. The method according to claim 11, wherein the pixel position from which the background history is reallocated is based on the motion detected by a motion sensor of the imaging device.

13. The method according to claim 11, wherein the pixel position from which the background history is reallocated is based on a zoom value of the imaging device.

14. The method according to claim 11, wherein the pixel position from which the background history is reallocated is determined based on a correspondence obtained by a block matching algorithm.

15. The data processing device programmed so as to carry out an image background recognition method according to claim 1.

16. The imaging device with an embedded data processing device according to claim 15.

17. The video-surveillance system comprising at least one imaging device and a data processing device according to claim 15.

18. The videogame system comprising at least one imaging device and a data processing device according to claim 15.

19. The data storage medium comprising a set of instructions for a data processing device to carry out an image background recognition method according to claim 1.