Survey on Background Identification Using Various Algorithms

Survey on Background Identification Using Various Algorithms

S. M. Dhanya

Student of M.E VLSI Design

Sri Ramakrishna Engineering College Coimbatore, India

N. Kirthika Assistant Professor,

Department of ECE (PG- VLSI Design Sri Ramakrishna Engineering College Coimbatore, India

Abstract The background identification is one of the important task in determining the moving object. The tracking of moving object and persons is commonly used in traffic monitoring. The common method for real-time segmentation of moving regions in image sequences involves background subtraction or thresholding. This paper discuss about various algorithms used for identifying the background. This results in a stable, real time outdoor tracker which reliably deals with changes in the lighting, repetitive motions from clutter, and changes in long-term scene.

KeywordsBackground Subtraction; Gaussian Mixture Model (GMM); Median filter and Approximate Median Filter

1. INTRODUCTION

   Background subtraction is mainly used to identify the background changes. They are mainly used in surveillance and traffic monitoring systems. Background subtraction is a widely used approach for detecting moving objects. Background subtraction is also called as Foreground detection. Image's foreground is extracted for recognizing objects. When we are exposed to reflection, animated changes, wind, rain or illumination changes brought by weather there will be changes in the background. Detecting the moving objects from the difference between the current frame and a reference frame is called as background image. Background subtraction methods have to deal with several problems and limitations in realistic environments. Each of them is discussed below.

   Quick illumination changes alter the color characteristics of the background, and also increase the deviation of background pixel. This results in increase in number of falsely detected foreground regions. Relocation of the background Object causes change in newly acquired position and previous position of the image. In this case only the newly acquired should be identified as foreground region. Initialization with moving objects: During initialization if moving objects are present during initialization then part of the background is occupied by moving objects. So during initialization there should be no moving objects. Shadows Objects can also cast shadows that might also be classified as foreground due to the illumination change in the shadow region.

   Most Background Subtraction algorithms work well under simple conditions there are various challenges that affect the output of the system. These challenges are system limitation and environmental challenges. System limitations are related to memory consumption and computational speed. This paper

   we compare various popular background subtraction algorithms such as Median filtering, Approximate Median Filter and Gaussian Mixture Model (GMM). We evaluated accuracy, speed and memory consumption of the above mentioned algorithms. The general flow of background subtraction is shown in the Figure1.

   INPUT IMAGES

   PRE PROCESSING

   BACKGROUNDMODELING

   THRESHOLDING AND SUBTRACTION

   DATA VALIDATION

   FOREGROUND DETECTION

   Fig.1. General flow of background subtraction

   The rest of this paper is organized as follows: Section II reviews on steps used in the Background subtraction algorithms; Section III is based on the review of Median Based Method, Section IV is based on the review of Approximate Median Method and Section V is based on the review of Gaussian Mixture Model. Finally, Section VI provides the Comparison results and conclusions.

2. BACKGROUND SUBTRACTION ALGORITHM REVIEW The first thing to perform background subtraction is to

   model it. The incoming frame is obtained and the background model is subtracted out. From this moving object is detected. This algorithm is called background subtraction. The efficiency of a background subtraction technique involves mainly three important steps: modelling, thresholding and data validation. Background modelling, is the backbone of the Background Subtraction algorithm, describes model representation and model adaption characteristics. Few algorithms are discussed below.

3. MEDIAN-BASED METHOD

   Median filtering is one of the most commonly used background modeling techniques. 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. Median filtering follows this basic prescription. The median filter was mainly used to reduce noise in an image, somewhat like the mean filter. This class of filter belongs to the class of edge preserving smoothing filters which are non-linear filters.

   These filters smoothes the data while keeping the small and sharp details. The median is just the middle value of all the values of the pixels in the neighborhood. This is not the same as the average (or mean); instead, the median has half the values in the neighborhood larger and half smaller. The median is a stronger "central indicator" than the average. In particular, the median is hardly affected by a small number of discrepant values among the pixels in the neighborhood. Consequently, median filtering is very effective at removing various kinds of noise. The background equation of the median filter can be represented by (1)

   Bt = U It , Itt , . , It n1 t (1)

   frame is incremented by one if the background pixel is less than the new pixel or decremented by one if larger. A pixels present in the background model effectively converges to a value where half of the incoming pixels are larger and half are smaller than its value. This value is called as the median. The Approximate median method will be selected, if it handles slow movements, which are often used in our environment. It also compares the current frame to the identified frame and the results are found by (2) is given below.

   bw x, y bg x, y > T (2)

   Where bw is the current pixel and bg is the background pixel. The computational time and memory consumption of the system is reduced. The main drawback of this Median Based method is the adaptive rate, which needs a large amount of time to learn a new background as the background changes.

   V. GAUSSIAN MIXTURE MODEL

   A Gaussian Mixture Model (GMM) is a parametric probability density function which is represented as a weighted sum of Gaussian component densities. Instead of modeling the values of all the pixels as one particular type of distribution, we model the pixel as mixture of Gaussian. Based on the parameters such as mean, weight and the variance of each of the Gaussians of the mixture, we can determine whether it correspond to background colors or foreground. The model adapts to changes in the lighting, repetitive motions in the scene, tracking through cluttered objects, slow- moving objects, and also for inserting or removing objects from the scene. Longer time is needed for slow moving object because of the variations in color. When the surface is under particular lighting condition then a single Gaussian will be enough. When the lighting conditions get changed over the time we need mixture of Gaussian.

   A Gaussian mixture model is defined as the weighted sum

   U is the updating model, where It

   is the frame at time [4].

   of M component Gaussian densities [2]. It is given by (3).

   Buffer size and the frame rate are the critical issues thataffect the performance of the filter.

   The median is calculated by first sorting all the pixel values from the surrounding neighborhood into numerical order and then replacing the pixel being considered with the middle pixel value. The median filter removes both the noise and the fine detail since it can't tell the difference between the two.

   p x ) = M w g x µ , (3)

   i=1 i i i

   Where x is a continuous-valued D-dimensional data vector, wi are the weight of the mixture, and g(x|i,i) are the component Gaussian and i ranges from 1 to M and it is given by the equation (4) .

   g x µ , i = 1 exp 1 (x µ ) 1 (x µ ) (4)

   Anything relatively small in size compared to the size of

   i 2D /2| i | 1/2

   2 i i i

   the neighborhood will have minimal affect on the value of the median, which can be filtered out. The median filter can't distinguish noise from the fine detail. The assumption is that the pixel stays in the background for more than half of the frames in the buffer [5]. Median filtering follows this basic prescription. This filter is mainly used to reduce noise in an image, somewhat like the mean filter. It is a recursive technique which stores previous video frames in a buffer and the background is estimated based on the variations in the pixel.

4. APPROXIMATE MEDIAN METHOD

   It is a complimentary method to median filtering and it is a recursive technique [6, 7]. Each pixel in the background model is compared to the corresponding pixel in the current

   Where i is the mean vector and i is the covariance matrix. Sum of the weights satisfy the condition M wi= 1. The complete Gaussian mixture model can be parameterized by the vector mean, mixture weights and covariance matrices from all component densities. The parameters are collectively represented as (5)

   i=1

   = wi, µi , i i = 1, M (5)

   We model each pixel as a Mixture of Gaussian. If the pixel does not fit the background then it is considered as foreground. If the K distribution does not match then it is replaced with current pixel. The background identification blocks are shown and processed by the equations in [1].

   The Match condition can be represented using equation. We need Variance and calculation of standard deviation with a square root circuit. The overall block diagram for background subtraction using GMM Algorithm is shown in the Figure 2. The function and operation of each and every block is explained in the following subdivision.

   1. Learning Rate

      The learning rate calculated using the (6) is shown below.

      n(k,t) = log2 k,t (6)

      This k,t is approximated by wk,t

   2. Ifitness

   IFk,t is the square of the inverse of the Fk,t factor. It is represented as given below:

   E. Weight, Mean,Variable,Matchsum and No_Mtch:

   The weight, Mean, Variance, Matchsum and no Match conditions can be updated by the following equations for Matched distribution:

   µk,t+1 = µk,t + k,t . pixel µk,t (9) 2k,t+1 = 2k,t + k,t . [ pixel µk,t )2 2k,t (10) wk,t+1 = wk,t w . wk,t + w (11) matchsumk,t+1 = matchsumk,t + 1 (12)

   For unmatched condition the mean and variance are unchanged but the weights are updated as follow

   1. Match

      IF k,t

      = 1 2

      Fk ,t

      (7)

      wk,t+1 = wk,t w . wk,t (13)

      During the no match condition the parameters are updated as follows

      The Match condition can be represented using equation.

      Mk = 1 if(pixel µk,t )2 < 6,25. k,t2 (8)

      We need Variance and calculation of standard deviation with a square root circuit.

      µk,t+1 = pixel (14)

      matchsumk,t+1 = 1 (15)

      2k,t+1 = vinit (16)

      k,t+1

      w = 1 msumtot

      (17)

      Here vinit is fixed value and msumtot is the sum of the matchsum.

      1. RESULTS AND DISCUSSIONS

         The comparison of different algorithm on MATLAB software has been done. Each algorithm was applied to four different challenging image sequences [3]. The first scenario (S1) represents color similarity. In the second scenario (S2) represent small movements in background. The third scenario (S3) shows illumination changes. The Fourth scenario (S4) represents crowded area with complete dynamic scene. Low level pixel-based evaluations were computed for each data set and we measure False Positive (FP), False Negative (FN) and Percentage of Correct Classification (PCC) for each set of data. The False Positive (FP) is the number of non-changed pixel that are incorrectly identified as changed pixels and the False Negative (FN) is the number of changed pixel that are identified as unchanged pixel. Percentage of Correct Classification (PCC) is overall correct identification [19].The PCC and CD is calculated using the equation

         Fig. 2. Background identification circuit

         PCC = CD

         CD +FD +FN

         (18)

   2. Control Logic

   Control logic Sorts the Gaussians in increasing IFk,t order and updates the equation. The output signals G1, G2, and G3 which represents the first, second, and third of the three Gaussian in increasing order of IFk,t. Where NM (No-Match) and GU (Gaussian Update) are updated based on this. When NM is 0 it is matched distribution else it is no match distribution.

   CD = Total Pixel FN + FP (19)

   TABLE I. MEMORY USAGE AND SPEED OF THE SELECTED

   Algorithm	Speed (frame per second)	Memory Usage (KB)
   Median Filtering	0.18 fps	10754 KB
   Approximation Median	0.17 fps	1670 KB
   GMM	0.60 fps	2304KB

   ALGORITHMS

   1. CONCLUSION

In this paper we have compared three well known algorithms in four challenging situation. The evaluation of these different algorithms proves that the GMM algorithm gives good accuracy and high speed compared to other algorithms. So GMM is the best compared to the other two algorithms.

Fig. 3. Comparison of results of various Background algorithms

TABLE I contains information about the memory consumption and computational time for the chosen algorithms. The results of various algorithms are compared in the table. This table shows that GMM (Gaussian Mixture Model) is faster than other algorithms. The results of various algorithms are shown in the Table II.

TABLE II. COMPARISON RESULT OF VARIOUS ALGORITHMS

REFERENCES

1. Mariangela Genovese and Ettore Napoli ASIC and FPGA Implementation of the Gaussian Mixture Model Algorithm for Real- Time Segmentation of High Denition Video IEEE Transactions on very large scale integration (vlsi) systems, vol. 22, no. 3, march 2014

2. Stauffer and W. E. L. Grimson, Adaptive background mixture models for realtime tracking, in Proc. IEEE Comput. Soc. Conf. Comput. Vis.Pattern Recognit., vol. 2 Fort Collins, CO, USA, Jun. 1999, pp. 1 7.

3. http://research.microsoft.com/jckrumm/WallFlower/TestImages.htm.

4. Cucchiara, Grana, Piccardi, Prati, Detecting moving objects, ghosts and shadows in video streams", IEEE Transactions on Pattern Analysis and Machine Intelligence, (vol. 25, no. 10), October 2003, pp. 1337

5. Cucchiara, Grana, Piccardi, Prati, Detecting Objects, Shadows and Ghosts in Video Streams by Exploiting Color and Motion Information", in Proc. of ICIAP 2001, 11th International Conference on Image Analysis and Processing, Palermo, Italy, September 26 2001, pp. 360.

6. Parks, D. H., Fels, S. S Evaluation of Background Subtraction Algorithms with Post-Processing. AVSS '08 Proceedings of the 2008 IEEE Fifth International Conference on Advanced Video and Signal Based Surveillance IEEE Computer Society Washington, DC, USA, 2008, pp. 192199.

7. Piccardi, M. Background Subtraction Techniques: a Review". Systems, Man ad Cybernetics, 2004 IEEE International Conference on, 07 March 2005, vol. 4.