Design Article
Background subtraction, part 1: MATLAB models
Seth Benton
8/10/2008 12:00 PM EDT
Introduction
Many DSP designs start out in MATLAB and are then translated into C. Unfortunately, MATLAB has a number of quirks that make this translation a headache. MATLAB extends arrays without programmer intervention. It organizes matrices in column major order, while C uses row major order. It uses vector math which must be translated into loops. It indexes the first element of an array with '1' instead of '0'. And so on. All this leads to an error-prone, time-consuming translation process that typically doesn't begin until the MATLAB is 100% verified— lest the C programmers waste valuable time hunting MATLAB bugs.
So when Catalytic (now Agility), released their MATLAB to C tool (MCS) in early 2006, I was intrigued. As were the readers of the DSP DesignLine, where articles on automatic MATLAB to C conversion are some of the site's most popular.
Wanting to see what all the fuss was about, I contacted Agility and obtained an evaluation copy to try it out for myself.
Because MCS targets image/video processing, I chose to implement three types of background subtraction—a common first step in many video processing applications. The algorithms were implemented from scratch in MATLAB, then converted to C using MCS. The C code was then verified in MATLAB using mex files. (All m-files, generated C files, and the test video clip used—can be downloaded here).
In Part 1 of this 2-part series, I'll give a brief overview of background subtraction and go into detail on the three methods I chose to implement: frame differencing, approximate median, and mixture of Gaussians. Part 2 illustrates the MATLAB to C conversion process and offers impressions of the tool.
Background Subtraction
As the name suggests, background subtraction is the process of separating out foreground objects from the background in a sequence of video frames. Background subtraction is used in many emerging video applications, such as video surveillance (one of today's hottest applications), traffic monitoring, and gesture recognition for human-machine interfaces, to name a few.
Many methods exist for background subtraction, each with different strengths and weaknesses in terms of performance and computational requirements. Most were developed in university labs over the last couple decades (I'm guessing 99% of them in MATLAB). Unfortunately, as is often the case in academia, many of these methods are currently impractical for commercial application. Eigen-analysis on 10 seconds of video? May earn you a PhD, but it'll probably never leave the lab. For this evaluation, my goal was to implement three methods that were
- Computationally efficient enough to make the leap from MATLAB to commercial application, and
- A good representation of background subtraction implementations in today's video applications.
Since background subtraction is being implemented on a wide range of hardware—and thus within a wide range of computational budgets—I chose to implement methods of varying complexity;
- Low-complexity, using the frame difference method,
- Medium complexity, using the approximate median method, and
- High-complexity, using the Mixture of Gaussians method.
The rest of this article focuses on detailing these three methods. For an overview of other background subtraction methods, this Power Point presentation gives a good high-level overview. For a more in-depth review and comparison of techniques, this paper is fairly comprehensive and was a good start for my MATLAB implementations.
Test video
I shot the test video at an intersection near my house in San Francisco California. My aim was not to obtain the most representative test video for a particular use case. Rather, I simply wanted to get the most challenging video I could and see how the different methods handled it. As seen in Figure 1, the video contains many challenging elements, including traffic moving at fast and slow speeds, pedestrians, bicyclists, changes in light levels, and a waving rainbow flag. The video was shot at VGA resolution (640x480), 30 frames per second. Because background subtraction algorithms typically process lower resolution grayscale video, I converted the video to grayscale and scaled it to QVGA (320x240).
Comments
tlee@sp
8/12/2008 10:46 PM EDT
I found the article informative in that different approaches were compared and videos were available. The code was a definite plus.
Please keep up the good work Seth!
Sign in to Reply
MDN
11/13/2008 1:23 AM EST
Hello sir,
I found your article very useful.Can you please suggest me how would I improve the perfomance of a video using approximate median filter when there is a large change in the background.
Thanks,
Santosh
Sign in to Reply
ximulka
5/5/2009 7:38 AM EDT
Thanks very much, it was veeeery useful for my research!
Sign in to Reply
ximulka
5/19/2009 6:11 AM EDT
Could you write the name of the paper that you based the MoG algorithm on? I'm trying to adopt it for audio background detection, and it would be very useful for me. Thanks
Sign in to Reply
sairam33
6/19/2009 11:36 AM EDT
hello sir,
The article was very useful for my studies.how can we improve the speed of mixture of gaussians
Sign in to Reply
Laplace Jr.
11/13/2009 7:48 PM EST
Very nice article, it is so helpful for my research.
Thanks so much for sharing this ...
Laplace Jr.
Sign in to Reply
Thierry17
3/24/2010 8:39 AM EDT
A complete survey on background subtraction using GMM is available here:
http://hal.archives-ouvertes.fr/hal-00338206_v1/
and fuzzy version here:
http://hal.archives-ouvertes.fr/hal-00336512_v1/
best regards!
Thierry
Sign in to Reply
Thierry17
3/29/2010 2:41 AM EDT
Very nice article and more information are available in the following publication:
http://hal.archives-ouvertes.fr/docs/00/33/82/.../RPCS_2008.pdf
and fuzzy version of the GMM:
http://hal.archives-ouvertes.fr/hal-00336512_v1/
Best regards!
Thierry
Sign in to Reply
Thierry17
3/29/2010 2:45 AM EDT
A complete survey on background subtraction using GMM is available here:
T. Bouwmans, F. El Baf, Modeling of Dynamic Backgrounds by Type-2 Fuzzy Gaussians Mixture Models, MASAUM Journal of Basic and Applied Sciences, Volume 1, Issue 2, pages 265-277, September 2009.
T. Bouwmans, F. El Baf, B. Vachon, Background Modeling using Mixture of Gaussians for Foreground Detection - A Survey, Recent Patents on Computer Science, Volume 1, No 3, pages 219-237, November 2008.
Sign in to Reply
Thierry17
3/29/2010 2:47 AM EDT
A complete survey on background subtraction using GMM is available here:
T. Bouwmans, F. El Baf, B. Vachon, Background Modeling using Mixture of Gaussians for Foreground Detection - A Survey, Recent Patents on Computer Science, Volume 1, No 3, pages 219-237, November 2008.
and fuzzy version of the GMM:
T. Bouwmans, F. El Baf, Modeling of Dynamic Backgrounds by Type-2 Fuzzy Gaussians Mixture Models, MASAUM Journal of Basic and Applied Sciences, Volume 1, Issue 2, pages 265-277, September 2009.
Best regards!
Thierry
Sign in to Reply
tl20003
6/3/2010 3:40 AM EDT
Thank you very much. It is very useful.
But My I ask you. when I change your video clip to another video clip. The code make error.
"
??? Error using ==> readavi
Unable to locate decompressor to decompress video stream
Error in ==> aviread at 64
X = readavi(info.Filename,-1);
"
The video clips i download in this website "http://signal.ee.bilkent.edu.tr/VisiFire/Demo/SmokeClips/"
Can you help me?
Sign in to Reply
tl20003
6/3/2010 8:58 PM EDT
The main reason is my video clips. That video clips are not suitable for this code. I converted that video to AVI(video compression FFDS). Thank for your code.
Sign in to Reply
Ahmad52
6/4/2010 12:48 PM EDT
Thank you Sir
It is very much informative for me
But sir I did not understood in approximate median filter method that why the background is incremented and decremented by 1
and where is the role of median filtering in that code
And sir kindly can you tell me that can it be extended so that we can track a specific moving object not all
Thaks
Sign in to Reply
mdabibi
9/2/2010 8:56 AM EDT
i think it's because of the Video Clip in that site is not AVI Standard Form.you must convert it to AVI Standard Form.
mdabibi@gmail.com
Mohammad Dabibi
Sign in to Reply
Ahmad52
6/6/2010 10:52 AM EDT
Thank you Sir
It is very much informative for me
But sir I did not understood in approximate median filter method that why the background is incremented and decremented by 1
and where is the role of median filtering in that code
And sir kindly can you tell me that can it be extended so that we can track a specific moving object not all
Thanks
Sign in to Reply
mdabibi
9/1/2010 8:27 PM EDT
dear sirs,
I couldn't download Test video used for background subtraction .would you please send it to my email.
i need it very soon.
thx for all
email: mdabibi@gmail.com
mohammad dabibi
Sign in to Reply