Abstract: Based on the assumption that background appears with large appearance frequency, a new background reconstruction algorithm based on basic sequential clustering is proposed in this research. First, pixel intensity in period of time are classified based on mend basic sequential clustering. Second, merging procedure and reassignment procedure are run to classified classes. Finally, pixel intensity classes, whose appearance frequencies are higher than a threshold, are selected as the background pixel intensity value. So the improved algorithm can rebuilt the background images of various scenes. Compared with the background reconstruction method based on basic sequential clustering, the simulation results show that those near classes are avoided at all and the effect of input order of data has been reduced greatly in our method. And the background model can represent the scene well.
INTRODUCTION
Identifying moving objects from a video sequence is a fundamental and critical task in video surveillance, traffic monitoring and analysis. Several approaches are known to separate foreground from background. Background subtraction is a common approach to identifying the moving objects, especially, for a video sequence from a stationary camera. Pixels in the current frame that deviate significantly from the background are considered to be moving objects. Background reconstruction and foreground detection are two major steps in a background subtraction algorithm. Background reconstruction uses the new video frame to calculate and update a background model. Foreground detection then identifies pixels in the video frame that cannot be adequately explained by the background model and outputs them as a foreground mask. Present research focuses on background reconstruction.
A large number of background reconstruction methods for fixed cameras have been proposed in recent years. We classify background modeling techniques into approach based on background assumption (Long and Yang, 1990; Gloyer et al., 1995; Cucchiara et al., 2003; Kornprobst et al., 1999; Hou and Han, 2004; Xiao and Han, 2007), statistical model (Wren et al., 1997; Stauffer and Grimson, 1999; Javed et al., 2002; Lee et al., 2003; Zivkovic and Van, 2004; Elgammal et al., 2000) and prediction techniques (Ridder et al., 1995; Toyama et al., 1999).
A adaptive smoothness method (Long and Yang, 1990) based on the assumption that intensity of background is stable for a long period. Their method finds intervals of stable intensity and uses a heuristic which choose the longest, most stable interval as the one most likely to represent the background. Median filter is one of the most commonly-used background modeling techniques (Gloyer et al., 1995). The background estimate is defined to be the median at each pixel location of all the frames in the buffer. The assumption is that the pixel stays in the background for more than half of the frames in the buffer. An improved algorithm about Median filtering is presented in Cucchiara et al. (2003) that has been extended to color by replacing the median with the medoid. Assumed that background would be defined as the most often observed part over the sequence, they (Kornprobst et al., 1999) presented a approach to deal with the background reconstruction and motion segmentation based on Partial Differential Equations (PDE), the result is good, but their method is complex and the parameters are difficult to choose. These methods can reconstruct background even though foreground objects are present in the sequence and can avoid blending. Pixel Intensity Classification (PIC) is presented in Hou and Han (2004). The method assume that background pixel intensity appears in image sequence with the maximum probability, then classified pixels intensity based on the calculated pixel intensity difference between inter-frame, finally, the intensity value with the maximum frequency is selected as the background pixel intensity value. In this study a multi background reconstruction based on online cluster has been proposed. Our algorithm adopted the assumption that background wouldn`t be the part appear a short time of the sequence. In this approach, first, pixel intensity is classified based on online cluster, then cluster center and appear probability of each class is calculated, finally, a single or multi pixel intensity, with the appear probability is higher than a threshold, are selected as the background pixel intensity value. Based on the assumption that background appears with large appearance frequency, a background subtraction algorithm based on Basis Sequential Clustering (BSC) is proposed in literature (Xiao and Han, 2007). First, pixel intensity in period of time are classified based on basic sequential clustering and pixel intensity classes, whose appearance frequency is higher than a threshold, are selected as the background pixel intensity value. Simulation results show that the algorithm can hand complex situations contains small motions and motion detection can be performed correctly. It is obvious that the results of BSC are strongly dependent on the order in which the data are presented to the algorithm. And it may happen that two of the formed clusters are very closely located.
Some of the commonly-used statistic model are Time Averaged Background Image (TABI), Gaussian model (Wren et al., 1997; Stauffer and Grimson, 1999) and Non-parametric Model (Elgammal et al., 2000). A simple method of background reconstruction is TABI, a background approximation is obtained by averaging a long time image sequences, the method is effective in empty scene, once situations with many moving objects, especially if they move slowly and the foreground objects always can be blending into the background image. A single Gaussian (Wren et al., 1997) is considered to model the statistical distribution of a background pixel, it does not cope with multimodal backgrounds. Extended background subtraction approach (Stauffer and Grimson, 1999) by using an adaptive multi-modal subtraction method that modeled the pixel color as a Mixture of Gaussians (MOG). This method could deal with slow changes in illumination, repeated motion from background clutter and long term scene changes. But The MOG method is computationally intensive and its parameters require careful tuning. Literature (Javed et al., 2002; Lee et al., 2003; Zivkovic and Van, 2004) put forward kinds of modify, but computationally intensive has not solved yet. Adapted a multi-model background estimate (Elgammal et al., 2000) at each pixel location, Gaussian was chosen to be the kernel estimator and the method uses the median of the absolute differences between successive frames as the width of the kernel. The model can handle situations where the dynamic background but contains small motion. However, the method is computationally intensive and it is not easy to choose its parameters.
Kalman Filter (KF) (Ridder et al., 1995), Wiener filter (Toyama et al., 1999) for background reconstruction are based on prediction techniques. Ridder et al. (1995) modeled each pixel with Kalman Filter which made their system more robust to lighting changes in the scene, but the method recovers slowly and the foreground objects are easily to be blended into background. A simpler version of the Kalman filter called Weiner filter (Toyama et al., 1999), it is a linear predictor based on a recent history of values. Any pixel that different significantly from its predicted value are declared foreground.
THE STEPS OF THE IMPROVED BACKGROUND RECONSTRUCTION ALGORITHM
Literature (Hou and Han, 2004; Xiao and Han, 2007) reports the character of the pixel intensity in detail. We adopted the same assumption that was mentioned in literature (Xiao and Han, 2007), that background would not be the parts which appear in the sequence for a short time, a background reconstruction algorithm based on Basic Sequential Clustering (BSC) was proposed in this research. The steps of algorithm are described as follows:
Step 1: Classify the pixel intensity based on BSC.
The basic idea of BSC is the following: Starts with the guess that the first input value is the initial class and the number of the initial class set to 1. As each new data is considered, it is either assigned to an existing cluster or assigned to a newly created cluster, depending on its distance from the already formed ones. Let N be the frames that selected from the sequences and marked as F = {f1, f2, …, fN}. Pixel (x, y) is used to illustrate the BSC. The BSC is stated as Table 1.
Where, ft (x, y) represents the intensity value of the pixel
(x, y) of the t(t = 1, 2, …, N) frame.
Let δ represent a threshold. The following process is run to same pixel (x, y). The omission of pixel position is necessary for concise writing.
Step 2: Run merging procedure.
In basic sequential clustering algorithm, it may happen that two of the formed clusters are very closely located and it may be desirable to merge them into a single one.
| Table 1: | The BSC procedure |
| Table 2: | The Merging procedure |
Consider
the data F = {1, 11, 5, 10, 6, 9, 8, 4, 70, 100}. If we present the F
in the above order to the BSC and we set δ1 = 10, we obtain
C1 = {4, 9.5, 70, 100} and m1 = {4, 4, 1, 1}. We
can see
If the number of clusters is n after the termination of the BSC,
δ2 is a user-defined parameter that quantifies the closeness
of two clusters,
Step 3: Run reassignment procedure.
The other drawback of the BSC if their sensitivity to the order of presentation
of data. Suppose, for example, that in using BSC, f2 is assigned
to the first cluster
It is assume that there are p clusters after the termination of the merging
procedure,
Then the reassignment procedure may be stated as Table 3.
In this procedure, b (ft) denotes the closest to cluster.
Step 4: Calculate the appearance frequency of all clusters.
| Table 3: | The reassignment procedure |
| Table 4: | The background selection procedure |
Assume that q clusters are formed now. The appearance frequency of ith cluster:
(1) |
where,
Step 5: Select background of pixel.
In real scene, multi-surfaces often appear in the view frustum of a particular pixel and the lighting conditions are often changed, so choosing a single image as background always results in large errors in moving object detection. Motivated by the work of Stauffer and Grimson (1999), we choose a single or multi-images as the background images. Suppose there are R(R≤q) clusters with a larger appearance frequency in the video sequences. After removal those intensity clusters with a small appearance probability, then the R(R≤q) clusters are chosen as the multi-background images. The background selection procedure are showed as Table 4.
Where, δ3 is a user-defined parameter,
We must readjust appearance frequency of candidate backgrounds:
(2) |
SIMULATION RESULTS AND COMPARISONS
Two examples show the results of background reconstruction by using our algorithm. The results calculated by TABI, PIC (Hou and Han, 2004), MOG (Stauffer and Grimson, 1999) and BSC (Xiao and Han, 2007) are given in detail in literature (Xiao and Han, 2007). In the study, we only give the simulation results compare the algorithm of BSC and our method. In the simulation the parameters in BSC are chosen as: N = 100, δ = 13 and δc = 0.2. The parameters that are referred in our algorithm are chosen as: N = 100, δ1 = 13, δ2 = 13 and δ3 = 0.2. The video shows the pure detection results without any morphological operations, noise filtering and tracking information of targets.
Figure 1 is result of background reconstruction of synthetic sequence. Suppose that all pixels in 100 frames have values as Table 5. BSC results in two backgrounds have values (158.07, 165.8). From the simulation result, we can see the two backgrounds are very closely and we should merge them into a single one. However, our method construct only one suitable background has values 160, therefore, background reconstruction is performed correctly.
Figure 2 is an indoor sequence. One hundred frames are used to construct the background. The number of background is different in vary pixel, so we use black denote empty background. For example, suppose that pixel (1, 1) has three backgrounds B1 (1, 1), B2 (1, 1) and B3 (1, 1). Pixel (2, 2) has one background B1 (2, 2), which results in two empty backgrounds B2 (2, 2) and B3 (2, 2), so we can see black in B2 (2, 2) and B3 (2, 2). From the background image of BSC, we can see part of foreground (see the area that is masked with ellipse in Fig. 2(a1)) is considered as background. It is clear that our method leads to more reasonable results than BSC. Motion detections also show that false detection of our method is less greatly than BSC. The motion detections (Fig. 2(d1) and Fig. 2(d2), Fig. 2(e1) and Fig. 2(e2)) show that our method can eliminate the false motion detection.
| Table 5: | Intensity of pixel in 100 frames |
| Fig. 1: | Result of background reconstruction of synthetic sequence. (a)-(d) are fame #5, #15, #50 and #80 separately; (e) and (d) are the backgrounds B1 and B2 of BSC; (g) is the background of out method |
| Fig. 2: | Result of background reconstruction and motion detection
of Hall sequence. (a1)-(a4) are the backgrounds B1-B4
of BSC; (b1)-(b4) are the backgrounds B1-B4
of our method; (c1) and (c2) are frame #39 and #100; (d1) motion detection
of 39th frame of our method; (d2) motion detection of 39th frame of
BSC; (e1) motion detection of 100th frame of our method; (e2) motion
detection of 100th frame of BSC |
CONCLUSIONS
Background reconstruction is core of background subtraction. An improved background reconstruction based basic sequential clustering is proposed in the paper. The merging procedure and assigned procedure are used after the termination of the BSC algorithm. Our method algorithm has two traits: 1) background reconstruction does not need priori knowledge of scene. 2) the algorithm can consume a lot of time of computation and save memory requirements. In addition, those near classes are avoided at all and the effect of input order of data has been reduced greatly.