The 8th International Co~ference o~ INFOrmatics and Systems (INFOS2012) - 14-16 May

Computational Intelligence and Multimedia Computing Track

A New Combination Method for Background

Subtraction in Video Sequences
Neven Galal El-Gamal, Hossam EI-Din Moustafa, F. E.Z. Abou-Chadi
Faculty of Engineering Mansoura University
Communication Department,
Mansoura Egypt
Neven2985@hotmail.com, Hossam_moustafa@hotmail.com, fzmr4@hotmail.com

Abstract- Identifying moving objects from a video sequence handle multiple backgrounds, such as waving trees. The
is a fundamental and critical task in many computer-vision generalized Mixture of Gaussians (MOG) has been used to
applications. It is an important part of visual tracking systems. model complex, nonstatic backgrounds [2].
In this paper, a new algorithm for background subtraction has
been proposed and its performance was investigated and
compared. It is a combination of three background subtraction
algorithms; frame difference, approximated median, and
Mixture of Gaussian. Each algorithm first they are modified and
then a decision level fusion algorithm applied to the results. The
performances of these algorithms are compared before and after
combinations. It has been found that the percentage error for the
pixel in each frame has reduced remarkably when applying the
combinational algorithm.

I. INTRODUCTION Figure 1. Basic Steps for Background Subtraction Algorithms.

Identification of foreground objects and background
regions in a video is one of the fundamental tasks in computer
vision and video processing, especially in applications like The MOG has some disadvantages. Background having
video surveillance, traffic analysis and monitoring, video fast variations cannot be accurately modeled with just a few
coding, and tracking systems [1]. A common approach for Gaussians, causing problems for sensitive detection.
discriminating moving objects from the background scene is Median filtering is one of the most commonly-used
detection by background subtraction. The idea of background backgrounds modeling techniques [7]-[9]. The background
subtraction is to subtract or difference the current image from estimate is defined to be the median at each pixel location of
a reference background model. The subtraction leaves only all the frames in the buffer.The assumption is that the pixel
non-stationary or new objects [2]. stays in the background for more than half of the frames in the
Most of the background subtraction algorithms follow a buffer.
simple flow diagram shown in Fig.1 .The four major steps in a An approximated median filter is proposed [10]. In this
background subtraction algorithm are preprocessing, scheme, the running estimate of the median is incremented by
background modeling, foreground detection, and data one if the input pixel is larger than the estimate, and decreased
validation [3]. Many different approaches have been proposed by one if small. This estimate eventually converges to a value
for each of the four processing steps [4]. for which half of the input pixels are larger than and half are
The simplest background modeling technique is frame smaller than this value, that is, the median.
differencing [5]. It uses the video frame at time (t - 1) as the This paper proposes a new combinational method for
background model for the frame at time t. Since it uses only a background modeling. It relies on introducing some
single previous frame, frame differencing may not be able to modification in each of the three algorithms: frame difference,
identify the interior pixels of a large, uniformly-colored Mixture of Gaussian, approximated median, and then
moving object. This is commonly known as the aperture merging the outputs of the three techniques to obtain the
problem [6]. Frame differencing performs poorly if the output of the proposed combinational technique.
background is not truly static (e.g., fluttering leaves, water, The organization of the rest of the paper is as follows:
waves). Some background models assume that the series of Section 2 describes the frame difference method. The mixture
intensity values on a pixel can be modeled by a single of Gaussian method in Sec. 3. The approximated median
unimodal distribution. However, a single-mode model cannot method is discussed in Section 4. Sec. 5 presents the proposed

Faculty of Computers and Information - Cairo University MM-21

 The 8th International Conference on INFOrmatics and Systems (INFOS2012) - 14-16 May
Computational Intelligence and Multimedia Computing Track
algorithm and a comparative study of its performance with the III. MIXTURE OF GAUSSIAN METHOD
three other methods. Section 6 is the conclusion.

II.FRAME DIFFERENCE METHOD A more complex model was proposed that is mixture of
Gaussian to account for backgrounds containing animated
Frame differencing is one of the nonrecursive techniques textures (such as waves on the water or trees shaken by the
which maintains a buffer of video frames and uses a sliding- wind),
window approach for background estimation [5]. Video MOG model every pixel with a Mixture of K Gaussians.
frames can be stored into the buffer at a frame rate lower than [13] Thus, the probability of occurrence of a color at a given
the input rate. Fig.2 shows the main steps of frame difference pixel s is represented as:
method.

L
k

p(Is,t) = Wi,s,t·1](Is,t, Pi,s,t, Li,s,t) (3)

For all the frame sequence at time t (It), and it is assumed
that the estimated background: i=l
BG = It - 1 (1)
Then
where 11(Is,tJ Jli,s,tJ ~i,s,t) is the ith Gaussian model , r-i,s, t, the
(2) covariance matrix, K ranges from three to five and Wi,s,t its
weight.

The background is updated, before the foreground is detected,

as follows:
1. If It matches component i, i.e., It is within A standard
deviations of Jli.t then the ith component is updated as
follows
(4)
(5)
(6)

Where

2. Components which It do not match are updated by

G (7)

Figure 2. The Steps of the Frame Difference Algorithm [2].

(8)
(9)
alt = alt - 1
3. If It does not match any component, then the least
Fig. 3 shows the results obtained; the holes problem likely component is replaced With a new one which
appears clearly in the frames. To circumvent this problem and has 1J i,t = It Li,t large, and trJi,t low.
to minimize the percentage error; a number of steps were
After the updates, the weights trJi,t are renormalized; the
added to the original algorithm of the frame difference
foreground is detected as follows:
method.
All components in the Mixture are sorted into the order of
decreasing trJi,t/IlE i,t II .
So higher importance gets placed on
components with the most evidence and lowest variance;
which are assumed to be the background; Let

B = arqmuu, ~~
. (Lf=l Wi,t. > T ) (10)
Figure 3. The Results Obtained From the Frame Difference Algorithm. (a) L.z=l Wz,t
The Video Frame It ,(b) The Estimated Background It-I , and (c) The For some threshold T, Then components 1: B are assumed
Extracted Foreground.
to be background. So if It does not match one of these
components, the pixel is marked as foreground.

Faculty of Computers and Information - Cairo University MM-22

 The 8th International Conference on INFOrmatics and Systems (INFOS2012) - 14-16 May
. Computational Intelligence and Multimedia Computing Track
FIg. 4 sho~s the results o~tained; the holes problem method. The second step is to apply a data fusion procedure to
appears clearly In the frames which, our proposed algorithm the output of the three algorithms. This is described in Fig.6.
used to solve this problem
Frame Mixture of Approximated
Difference Gaussian Median

Figure 4. The Results Obtained From the Algorithm of Mixture of Gaussian.

(a) The Video Frame It, (b) The Estimated Background by Using Mixture of
Gaussian, and (c) The Extracted Foreground.

Figure 6. The Steps of the Proposed Algorithm.

IV. ApPROXIMATED MEDIAN METHOD
A. The Image Processing Step
Due to the success of non-recursive median filtering there As shown in Fig.3.c, Fig4.c, and Fig5.c the holes problem
is propose of a simple recursive filter to estimate the median. appears clearly. In order to circumvent this problem and to
Recursive techniques maintain a single background model that minimize the percentage error; a number of image processing
is updated with each new video frame. These techniques are steps were carried out to the output of each of the three
generally computationally efficient and have minimal memory algorithms as follows:
requirements [2]. The running estimate of the median is 1) Edge Detector
incremented by one if the input pixel is larger than the The first step is to apply an edge detection procedure to the
estimate, and decreased by one if smaller.[10] This estimate output of each of the three algorithms. Sobel function [11]
eventually converges to a value for which half of the input was chosen to detect frames transition.
pixels are larger than and half are smaller than this value, that 2) Dilate The Image
is, the median ,then the estimated background is set to be the The output of the edge detector shows lines of high contrast in
approximated median. the image. Some gaps are seen in the lines surrounding the
(11) object. These linear gaps can be disappeared if the Sobel
image is dilated using linear structuring elements, which can
Then FG = It - BG >T (12) be created using the Strel function.
The results of the approximated median method are shown in
3) Fill Interior Gaps
Fig.5. From the figure, it is clear that the holes problem is
The dilated image shows the outline of the object quite
present. So to circumvent this problem the proposed algorithm
clearly, but some holes still exist in the interior of the object.
was used.
To fill these holes imfill function in MATLAB program was
been used.
4) Smooth The Object
In order to make the segmented object look natural, the object
should be smoothed. This can be achieved by eroding the
image twice with a diamond structuring element [12]. The
diamond structuring element was created using the Strel
function. The object appears now clearly.
Fig. 8-10 show the results obtained from the frame difference
Figure 5. The Results of the Approximated Median Algorithm. (a) The Video method, mixture of Gaussian method, and approximated
Frame It, (b) The Estimated Background by Using Mixture of Gaussian, and
(c) The Extracted Foreground. median method after applying the above image processing
procedures. It can be noticed that the suggested image
V. THE PROPOSED ALGORITHM processing procedures give better and clearer object.
This algorithm consists mainly of two steps. The first step
is to apply some image processing procedure to the output of
each of the three algorithms: the frame difference method, the
Mixture of Gaussian method, and the approximated median

Faculty of Computers and Information - Cairo University MM-23

 The 8th International Conference on INFOrmatics and Systems (INFOS2012) - 14-16 May
Computational Intelligence and Multimedia Computing Track

Figure 8. The Frame Difference Method Results.(a) Edge Detector, (b) Dilate
the Image, Figure 12. The Extracted Foreground Using the Mixture of Gaussian
(c) Fill Interior Gapes, (d) Smooth the Object, and (e) The Extracted Method. (a)The Mixture of Gaussian Method Only and (b) the Processed
Foreground. Foreground.

Figure 9. The mixture of Gaussian Method. (a) Edge Detector, (b) Dilate the
Image,(c) Fill Interior Gapes, (d) Smooth the Object, and (e) The Extracted
Foreground. Figure 13. The Approximated Median Method. (a)Without Processing, and
(b) The Processed Foreground.

B. The Decision Level Fusion Algorithm

The three processed frames obtained from the three
background subtraction algorithms; frame difference, mixture
of Gaussian, and approximated median filter were then
merged using data fusion criteria [14]. This step improves the
resultant frame and reduces the percentage error as well.
Figure 10. The Approximated Median Method. (a) Edge Detector, (b) Dilate The visual inspection of Figs l1.b-13.b shows that there
the Image,(c) Fill Interior Gapes, (d) Smooth the Object, and (e) The are still some errors in these frames. Therefore, a decision
Extracted Foreground.
level fusion algorithm was utilized using the following Fusion
Rules:
Fig.II-13 show the object obtained from each of the three
algorithms: the frame difference method, the Mixture of if ((vl&v2) OR (vl&v3) OR (v2&v3)) is FG thi
Gaussian Method, the approximated median method and the FG (13)
processed output image of the each technique. It can be if ((vl&v2) OR (vl&v3) OR (v2&v3)) is BG thi
noticed that the suggested image processing procedure gives BG (14)
better and clearer object. Where:
VI: the output of the modified frame difference.
V2: the output of the modified Mixture of Gaussian.
V3:the output of the modified approximated median.
O(i,j): is the pixel (i,j) of the output.
C. Performance Measurements
The percentage error was calculated by using Eq.(15).
Using two fabricated videos with their corresponding separate
foreground video (fabricated by flash program; and then
converted to a video sequence)[15]. This foreground is
considered as the reference foreground f(i, j), and the output
Figure 11. The Extracted Foreground Using the Difference Method (a) of the three algorithms is O(i, j). The percentage error was
Without Processing, and (b) The Processed Foreground then calculated using (15).

LLIO(i,D - f(i,DI
n m

PEP(q) = (15)
i=l j=l
Where:
o (i,j) : is the pixel (i,j) of the output of each
algorithm after transforming it to black and white frames
F (i,j) : is the pixel(i,j) of the fabricated
video( accurate foreground).
N: number of column of the frame of the video.
M: number of raw of the frame of the video.

Faculty of Computers and Information - Cairo University MM-24

 The 8th International Conference on INFOrmatics and Systems (INFOS2012) - 14-16 May
Computational Intelligence and Multimedia Computing Track
q: length of the source video (number of frames). Experimental results on two fabricated videos demonstrate
PEP: average percentage error of the pixel in each that the proposed combinational algorithm eliminates the
frame. holes significantly and improves the resultant foreground.
Fig.14 and Fig.15 show the calculated error for the three
algorithms of background subtraction and the proposed REFERENCE
algorithm. As clear in the figures, the percentage error of the
proposed algorithm has the least magnitude compared to that [1] MingjunWu., XianrongPeng" Spatio-temporal context for
codebook-based dynamic background subtraction"
obtained from the three methods. The mixture of Gaussian Science Direct, Elsevier GmbH 2009.
gives the worst results. [2] S. Cheung and C. Kamath." Robust techniques for
background subtraction in urban traffic video". in Proc. of
the VCIP, 2004.
[3] J. Mike McHugh, Janusz Konrad, Venkatesh Saligrama,
and Pierre-Marc Jodoin" Foreground-Adaptive
Background Subtraction" IEEE SIGNAL PROC.2009.
[4] Mohamad Hoseyn Sigari, Mahmood Fathy "Real-time
Background modeling-Subtraction using Two-Layer
Codebook Model". IMECS 2008.
[5] Wan Zaki et al.: Moving object detection using key
point's reference model. EURASIP Journal on Image and
Video Processing 2011.
[6] Shireen Y. Elhabian , Khaled M. El-Sayed and Sumaya
H. Ahmed "Moving Object Detection in Spatial Domain
using Background Removal Techniques - State-of-Art"
Figure 14. The Percentage Error as a.F~~ti?n of Frame Number (Video 1). Recent Patents on Computer Science, Vol. 1, No. 1,2008.
[7] R. Cutler and L. Davis, "View-based detection," in
Proceedings Fourteenth International Conference on
Pattern Recognition, 1, pp. 495-500, (Brisbane,
Australia), Aug 1998.
[8] R. Cucchiara, M. Piccardi, and A. Prati, "Detecting
moving objects, ghosts, and shadows in video streams,"
IEEE Transactions on Pattern Analysis and Machine
Intelligence 25, pp. 1337-1342, Oct 2003.
[9] B. Lo and, S. Velastin , "Automatic congestion detection
system for underground platforms," in Proceedings of
2001 International symposium on intelligent multimedia,
video, and speech processing, pp. 158-161, (Hong Kong),
May 2001.
[10] N.J.B. McFarlane and C.P. Schofield," Segmentation and
tracking of piglets in images" Machine Vision and
Applications 8-187-193,1995.
Figure 15. Percentage Error as a Function of Frame Number (Video 2). [11] Tapas Kumar and G. Sahoo," A Novel Method of Edge
Detection using Cellular Automata", International Journal
Clearly from the performance measurements results curve of Computer Applications (0975 - 8887) Volume 9-
it appears that our proposed algorithms improves the No.4, November 2010.
[12] "detecting a cell using image segmentation", 5/5/2011,
performance measurements over all the video frames. http://www.docstoc.com/docs/78776244/Image_Segment
ation
VI. CONCLUSION [13] Y. Benezeth, P.M. Jodoin, B. Emile, H. Laurent and C.
Rosenberger," Review and Evaluation of Commonly-
In this paper, a new algorithm was introduced to validate Implemented Background Subtraction Algorithms", IEEE
foreground regions. The proposed algorithm consists mainly 978-1-4244-2175-6, 2008 .
of two steps. The first step is to apply some image processing [14] Vassilios Chatzis, Adrian G. Bor,s, and loannis Pitas,"
multimodal decision-level fusion for person
procedure to the output of each of the three algorithms: the authentication", IEEE transaction on systems, man , and
frame difference method, the Mixture of Gaussian method, cybernetics, VOL. 29, NO.6, NOV 1999.
and the approximated median method. The second step is to [15] "Convert SWF to AVI with Powerful Features",
apply a data fusion procedure to the output of the three http://www.avi-swf-convert.com.
algorithms.
It has been found that applying a number of image
processing steps to the output foreground image has been
improved to a great extent and the numbers of the holes have
been reduced greatly. The application of a decision level
fusion criterion to the three processed foregrounds obtained
from the three algorithms improves greatly the resulted
foreground. It has been found that the calculated percentage
error has been greatly reduced for the proposed technique.

Faculty of Computers and Information - Cairo University MM-25